Find the Number of K-Even Arrays - Problem

Dynamic Programming Medium

You are given three integers n, m, and k. An array arr is called k-even if there are exactly k indices such that, for each of these indices i (0 ≤ i < n - 1):

(arr[i] * arr[i + 1]) - arr[i] - arr[i + 1] is even.

Return the number of possible k-even arrays of size n where all elements are in the range [1, m]. Since the answer may be very large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: n = 3, m = 2, k = 1

› Output: 4

💡 Note: Arrays with exactly 1 even pair: [1,1,2], [2,1,1], [1,2,2], [2,2,1]. Each has one adjacent pair with same parity making (a*b-a-b) even.

Example 2 — No Even Pairs

$ Input: n = 2, m = 2, k = 0

› Output: 2

💡 Note: Arrays with 0 even pairs: [1,2], [2,1]. Different parities make (1*2-1-2)=-1 odd, (2*1-2-1)=-1 odd.

Example 3 — All Even Pairs

$ Input: n = 2, m = 2, k = 1

› Output: 1

💡 Note: Arrays with exactly 1 even pair: [2,2]. Only when both adjacent numbers are even does (a*b-a-b) become even: (2*2-2-2)=0.

Constraints

1 ≤ n ≤ 1000
1 ≤ m ≤ 1000
0 ≤ k ≤ n-1

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that (a×b - a - b) is even if and only if a and b have the same parity. Best approach uses 3D Dynamic Programming tracking position, last element's parity, and remaining k-even pairs needed. Time: O(n×k), Space: O(n×k)

Common Approaches

✓ Sliding Window

⏱️ Time: N/A Space: N/A

3D Dynamic Programming

⏱️ Time: O(n × k) Space: O(n × k)

Use 3D DP table dp[pos][parity][remaining_k] where parity tracks if last element is odd/even, and remaining_k tracks how many more even pairs we need.

Brute Force Recursion

⏱️ Time: O(m^n × n) Space: O(n)

Try every possible value for each position recursively. For each complete array, check if exactly k adjacent pairs satisfy the even condition.

Memoized Recursion

⏱️ Time: O(n × k × 2) Space: O(n × k × 2)

Use recursion with memoization to count arrays. Cache results based on current position, last element's parity, and remaining k-even pairs needed.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_STATES 100000

typedef struct {
    int pos;
    int lastParity;
    int remainingK;
    long long result;
} MemoEntry;

MemoEntry memo[MAX_STATES];
int memoSize = 0;

long long getMemo(int pos, int lastParity, int remainingK) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].pos == pos && memo[i].lastParity == lastParity && memo[i].remainingK == remainingK) {
            return memo[i].result;
        }
    }
    return -1;
}

void setMemo(int pos, int lastParity, int remainingK, long long result) {
    if (memoSize < MAX_STATES) {
        memo[memoSize].pos = pos;
        memo[memoSize].lastParity = lastParity;
        memo[memoSize].remainingK = remainingK;
        memo[memoSize].result = result;
        memoSize++;
    }
}

long long dp(int pos, int lastParity, int remainingK, int n, int oddCount, int evenCount) {
    if (pos == n) {
        return remainingK == 0 ? 1 : 0;
    }
    
    if (remainingK < 0) {
        return 0;
    }
    
    long long cached = getMemo(pos, lastParity, remainingK);
    if (cached != -1) {
        return cached;
    }
    
    long long result = 0;
    
    // Try odd numbers (parity 1)
    if (pos == 0) {
        result = (result + ((long long)oddCount * dp(pos + 1, 1, remainingK, n, oddCount, evenCount)) % MOD) % MOD;
    } else {
        int newK = (lastParity == 1) ? remainingK - 1 : remainingK;
        result = (result + ((long long)oddCount * dp(pos + 1, 1, newK, n, oddCount, evenCount)) % MOD) % MOD;
    }
    
    // Try even numbers (parity 0)
    if (pos == 0) {
        result = (result + ((long long)evenCount * dp(pos + 1, 0, remainingK, n, oddCount, evenCount)) % MOD) % MOD;
    } else {
        int newK = (lastParity == 0) ? remainingK - 1 : remainingK;
        result = (result + ((long long)evenCount * dp(pos + 1, 0, newK, n, oddCount, evenCount)) % MOD) % MOD;
    }
    
    result %= MOD;
    setMemo(pos, lastParity, remainingK, result);
    return result;
}

long long solution(int n, int m, int k) {
    int oddCount = (m + 1) / 2;
    int evenCount = m / 2;
    
    memoSize = 0;  // Reset memo
    
    return dp(0, -1, k, n, oddCount, evenCount);
}

int main() {
    int n, m, k;
    scanf("%d", &n);
    scanf("%d", &m);
    scanf("%d", &k);
    
    long long result = solution(n, m, k);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen