Google Intern OA Problems

Problem 1.
Given an array find no. of non-empty subsequences which does not have three consecutive odd or three consecutive even numbers in subsequence. Since answer is large print it modulo 1e9+7.
Expected time complexity is O(N) or (ONlogN).

hint

code

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 1000000007;

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

    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    // dp[k][i][j]: number of subsequences using first k elements
    // where the last two parities are (i, j), with:
    // 0 = none, 1 = even, 2 = odd
    vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(3, vector<long long>(3, 0)));
    dp[0][0][0] = 1; // Base case: empty subsequence

    for(int k = 0; k < n; k++){
        int p = (a[k] % 2 == 0 ? 1 : 2);
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                // Case 1: don't take a[k]
                dp[k + 1][i][j] = (dp[k + 1][i][j] + dp[k][i][j]) % MOD;

                // Case 2: take a[k] if it doesn't form 3 same parity
                if (!(i == j && j == p)) {
                    dp[k + 1][j][p] = (dp[k + 1][j][p] + dp[k][i][j]) % MOD;
                }
            }
        }
    }

    // sum over all final dp[n][i][j] and subtract empty subsequence
    long long ans = 0;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            ans = (ans + dp[n][i][j]) % MOD;
        }
    }
    ans = (ans - 1 + MOD) % MOD;

    cout << ans << "\n";
    return 0;
}

Problem 2.
A number X is said to be palindrome special, if every digit i present in X occurs exactly i times and digits of X form a palindrome, you are given t test cases (<=1e5) and in each test case integer N(<=1e17). Find nearest greater no. which is a special palindrome.

hint

code