logoChat01.ai

in cpp Count subsequences You are given an array A...

Created on: July 5, 2025

Answered using O3 by Chat01

Question

in cpp
Count subsequences
You are given an array A of N integer elements.
Task
Determine the number of the non-empty subsequences of array A such that there do not exist three consecutive even or three consecutive odd integers in the subsequence. As the answer can be large, print it modulo 109 + 7.
Notes
Assume 1-based indexing.
A subsequence of array A can be obtained by deleting some array elements while keeping the order of other elements intact

Thought

Considering C++ solution

The user is asking to count non-empty subsequences in an array with restrictions on consecutive evens and odds. They mentioned C++, so it seems they want a C++ solution.

I’ll suggest a dynamic programming approach. The constraints are likely to require an O(N) solution, so it’ll use dynamic programming to efficiently count subsequences.

I’ll write the solution with a focus on saving the number of valid subsequences, considering consecutive odd and even integrals, avoiding three consecutive of either type. Let me get the solution ready!

Building subsequences with constraints

I need to find the count of subsequences that meet the constraint of no three consecutive even or odd numbers. To solve this, I’ll use dynamic programming (DP).

I’ll maintain states that track the sequence’s current parity and length, using four possible states for even and odd values. As I iterate over the array, I’ll update the states based on whether the current element continues a sequence or forms a new subsequence. The transitions depend on the last two parity values and lengths.

I’ll apply modular arithmetic for the result.

Thought for 15 seconds

Answer

Below is an O(N) time / O(1) memory dynamic-programming solution in modern C++.
The key idea is to remember, for every valid subsequence we have built so far, only the parity of its last two selected elements matters:

StateMeaning
e1subsequences that end with one even in a row (…E)
e2subsequences that end with two evens in a row (…EE)
o1subsequences that end with one odd in a row (…O)
o2subsequences that end with two odds in a row (…OO)

When we scan the next element x:

  • Start a new subsequence containing only x.
  • Append x to every subsequence whose current tail parity differs – the run length resets to 1.
  • Append x to every subsequence whose tail parity equals x’s parity and whose run-length is 1 – the run length becomes 2.
  • Sub-sequences that skip x simply stay in their old state.

Because we never allow a run length to reach 3, all generated subsequences are valid.

cpp
#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1'000'000'007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    vector<long long> A(N);
    for (auto &v : A) cin >> v;

    long long e1 = 0, e2 = 0, o1 = 0, o2 = 0;          // DP states

    for (long long x : A) {
        if ((x & 1) == 0) {                 // x is even
            long long add_e1 = (1 + o1 + o2) % MOD; // new subseq + extend odd-ending ones
            long long add_e2 = e1;                   // extend …E to …EE

            e1 = (e1 + add_e1) % MOD;
            e2 = (e2 + add_e2) % MOD;
        } else {                          // x is odd
            long long add_o1 = (1 + e1 + e2) % MOD; // new subseq + extend even-ending ones
            long long add_o2 = o1;                   // extend …O to …OO

            o1 = (o1 + add_o1) % MOD;
            o2 = (o2 + add_o2) % MOD;
        }
    }

    long long ans = (e1 + e2 + o1 + o2) % MOD;       // all non-empty valid subsequences
    cout << ans << '\n';
    return 0;
}

Why it works

  • A subsequence’s legality depends only on the parity streak at its tail. By compressing every subsequence into one of the four DP buckets above, we count all possibilities without double-counting.
  • Each array element is processed once; every state update is O(1).

Complexity

  • Time: O(N)
  • Memory: O(1) (just four integers)

Prints the answer modulo 1 000 000 007 as required.

Question

int solve(int N, vector<int> A)
write the code in this function only

Thought

Writing C++ solve function

The user wants just the solve function without the full code. They need to count subsequences with no three consecutive numbers of the same parity (even or odd). I'll structure it by handling even and odd numbers, updating the counts at each step, and taking mod 1,000,000,007. I'll use dynamic variables for even and odd cases (e1, e2,

Thought for a few seconds

Answer

cpp
int solve(int N, std::vector<int> A) {
    constexpr long long MOD = 1'000'000'007LL;

    long long e1 = 0, e2 = 0, o1 = 0, o2 = 0;   // DP buckets

    for (int x : A) {
        if ((x & 1) == 0) {          // even
            long long add_e1 = (1 + o1 + o2) % MOD;   // start new or extend odd-ending
            long long add_e2 = e1;                    // extend …E to …EE

            e1 = (e1 + add_e1) % MOD;
            e2 = (e2 + add_e2) % MOD;
        } else {                       // odd
            long long add_o1 = (1 + e1 + e2) % MOD;   // start new or extend even-ending
            long long add_o2 = o1;                    // extend …O to …OO

            o1 = (o1 + add_o1) % MOD;
            o2 = (o2 + add_o2) % MOD;
        }
    }

    return static_cast<int>((e1 + e2 + o1 + o2) % MOD);   // all non-empty valid subsequences
}

Share this Q&A