Find the Number of K-Even Arrays - Practice Coding Problems

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: 2

💡 Note: Arrays with exactly 1 even pair: [1,1], [2,2]. Same parities: (1*1-1-1)=-1 is odd, wait... (1*1-1-1)=-1. Actually (2*2-2-2)=0 is even.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

n=3, m=2, k=1 (array length 3, values 1-2, need 1 even pair)

Process

Check all arrays for pairs with same parity

Output

Count arrays with exactly k=1 even pairs

Key Takeaway

🎯 Key Insight: The expression (a×b - a - b) is even if and only if a and b have the same parity

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

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(m^n × n)	O(n)	Generate all possible arrays and count k-even ones
Memoized Recursion	O(n × k × 2)	O(n × k × 2)	Add memoization to avoid recomputing subproblems
3D Dynamic Programming	O(n × k)	O(n × k)	Bottom-up DP with states for position, last parity, and k count

Brute Force Recursion — Algorithm Steps

Try all m values for each position
For complete arrays, count even pairs
Return count of arrays with exactly k even pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Try all m values for each position

Validate

Count even pairs in complete arrays

Count

Sum arrays with exactly k even pairs

Code -

solution.c — C

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

#define MOD 1000000007

int isEvenPair(int a, int b) {
    return (a * b - a - b) % 2 == 0;
}

int backtrack(int pos, int* arr, int n, int m, int k) {
    if (pos == n) {
        int evenCount = 0;
        for (int i = 0; i < n - 1; i++) {
            if (isEvenPair(arr[i], arr[i + 1])) {
                evenCount++;
            }
        }
        return evenCount == k ? 1 : 0;
    }
    
    long long total = 0;
    for (int val = 1; val <= m; val++) {
        arr[pos] = val;
        total = (total + backtrack(pos + 1, arr, n, m, k)) % MOD;
    }
    return (int)total;
}

int solution(int n, int m, int k) {
    int* arr = (int*)malloc(n * sizeof(int));
    int result = backtrack(0, arr, n, m, k);
    free(arr);
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(m^n × n)

Generate m^n arrays, each taking O(n) time to validate

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth of n for array construction

⚡ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler