Find the Number of K-Even Arrays

Problem

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 109 + 7.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


Input: n = 3, m = 4, k = 2
Output: 8
Explanation:
The 8 possible 2-even arrays are:
* `[2, 2, 2]`
* `[2, 2, 4]`
* `[2, 4, 2]`
* `[2, 4, 4]`
* `[4, 2, 2]`
* `[4, 2, 4]`
* `[4, 4, 2]`
* `[4, 4, 4]`

Example 2:

1
2
3
4


Input: n = 5, m = 1, k = 0
Output: 1
Explanation:
The only 0-even array is `[1, 1, 1, 1, 1]`.

Example 3:

1
2


Input: n = 7, m = 7, k = 5
Output: 5832

Constraints:

1 <= n <= 750
0 <= k <= n - 1
1 <= m <= 1000

Solution

Method 1 – Dynamic Programming with Parity Tracking

Intuition

The key is to count arrays where exactly k pairs of adjacent elements satisfy (arr[i] * arr[i+1]) - arr[i] - arr[i+1] is even. This expression is even if and only if arr[i] and arr[i+1] have the same parity (both even or both odd). We can use dynamic programming to count the number of arrays with exactly k such adjacent pairs.

Approach

Let odd be the count of odd numbers in [1, m], and even be the count of even numbers in [1, m].
Define dp[i][j][p] as the number of arrays of length i, with j k-even pairs, ending with parity p (0 for even, 1 for odd).
Initialize dp[1][0][0] = even, dp[1][0][1] = odd.
For each position i from 2 to n, for each j from 0 to k, and for each parity p:
- If the previous parity is the same as p, increment j (since the pair is k-even).
- Otherwise, j stays the same.
- Transition:
  - dp[i][j][p] += dp[i-1][j-(p==q)][q] * (even if p==0 else odd) for q in {0,1}.
The answer is dp[n][k][0] + dp[n][k][1] modulo 10**9 + 7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
    int numberOfKEvenArrays(int n, int m, int k) {
        const int MOD = 1e9 + 7;
        int odd = (m + 1) / 2, even = m / 2;
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(k + 1, vector<int>(2)));
        dp[1][0][0] = even;
        dp[1][0][1] = odd;
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                for (int p = 0; p < 2; ++p) {
                    int cnt = (p == 0) ? even : odd;
                    for (int q = 0; q < 2; ++q) {
                        int add = (p == q) ? 1 : 0;
                        if (j >= add)
                            dp[i][j][p] = (dp[i][j][p] + 1LL * dp[i-1][j-add][q] * cnt) % MOD;
                    }
                }
            }
        }
        return (dp[n][k][0] + dp[n][k][1]) % MOD;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


func numberOfKEvenArrays(n, m, k int) int {
    mod := int(1e9 + 7)
    odd, even := (m+1)/2, m/2
    dp := make([][][]int, n+1)
    for i := range dp {
        dp[i] = make([][]int, k+1)
        for j := range dp[i] {
            dp[i][j] = make([]int, 2)
        }
    }
    dp[1][0][0] = even
    dp[1][0][1] = odd
    for i := 2; i <= n; i++ {
        for j := 0; j <= k; j++ {
            for p := 0; p < 2; p++ {
                cnt := even
                if p == 1 {
                    cnt = odd
                }
                for q := 0; q < 2; q++ {
                    add := 0
                    if p == q {
                        add = 1
                    }
                    if j >= add {
                        dp[i][j][p] = (dp[i][j][p] + dp[i-1][j-add][q]*cnt) % mod
                    }
                }
            }
        }
    }
    return (dp[n][k][0] + dp[n][k][1]) % mod
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
    public int numberOfKEvenArrays(int n, int m, int k) {
        int MOD = 1000000007;
        int odd = (m + 1) / 2, even = m / 2;
        int[][][] dp = new int[n + 1][k + 1][2];
        dp[1][0][0] = even;
        dp[1][0][1] = odd;
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                for (int p = 0; p < 2; ++p) {
                    int cnt = (p == 0) ? even : odd;
                    for (int q = 0; q < 2; ++q) {
                        int add = (p == q) ? 1 : 0;
                        if (j >= add)
                            dp[i][j][p] = (int)((dp[i][j][p] + 1L * dp[i-1][j-add][q] * cnt) % MOD);
                    }
                }
            }
        }
        return (dp[n][k][0] + dp[n][k][1]) % MOD;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
    fun numberOfKEvenArrays(n: Int, m: Int, k: Int): Int {
        val MOD = 1_000_000_007
        val odd = (m + 1) / 2
        val even = m / 2
        val dp = Array(n + 1) { Array(k + 1) { IntArray(2) } }
        dp[1][0][0] = even
        dp[1][0][1] = odd
        for (i in 2..n) {
            for (j in 0..k) {
                for (p in 0..1) {
                    val cnt = if (p == 0) even else odd
                    for (q in 0..1) {
                        val add = if (p == q) 1 else 0
                        if (j >= add)
                            dp[i][j][p] = (dp[i][j][p] + dp[i-1][j-add][q].toLong() * cnt % MOD).toInt()
                    }
                }
            }
        }
        return (dp[n][k][0] + dp[n][k][1]) % MOD
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def numberOfKEvenArrays(self, n: int, m: int, k: int) -> int:
        MOD = 10**9 + 7
        odd = (m + 1) // 2
        even = m // 2
        dp = [[[0, 0] for _ in range(k + 1)] for _ in range(n + 1)]
        dp[1][0][0] = even
        dp[1][0][1] = odd
        for i in range(2, n + 1):
            for j in range(k + 1):
                for p in range(2):
                    cnt = even if p == 0 else odd
                    for q in range(2):
                        add = 1 if p == q else 0
                        if j >= add:
                            dp[i][j][p] = (dp[i][j][p] + dp[i-1][j-add][q] * cnt) % MOD
        return (dp[n][k][0] + dp[n][k][1]) % MOD

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


impl Solution {
    pub fn number_of_k_even_arrays(n: i32, m: i32, k: i32) -> i32 {
        let n = n as usize;
        let m = m as usize;
        let k = k as usize;
        let odd = (m + 1) / 2;
        let even = m / 2;
        let mut dp = vec![vec![vec![0i64; 2]; k + 1]; n + 1];
        dp[1][0][0] = even as i64;
        dp[1][0][1] = odd as i64;
        let MOD = 1_000_000_007i64;
        for i in 2..=n {
            for j in 0..=k {
                for p in 0..2 {
                    let cnt = if p == 0 { even } else { odd } as i64;
                    for q in 0..2 {
                        let add = if p == q { 1 } else { 0 };
                        if j >= add {
                            dp[i][j][p] = (dp[i][j][p] + dp[i-1][j-add][q] * cnt) % MOD;
                        }
                    }
                }
            }
        }
        ((dp[n][k][0] + dp[n][k][1]) % MOD) as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    numberOfKEvenArrays(n: number, m: number, k: number): number {
        const MOD = 1e9 + 7;
        const odd = Math.floor((m + 1) / 2);
        const even = Math.floor(m / 2);
        const dp = Array.from({ length: n + 1 }, () => Array.from({ length: k + 1 }, () => [0, 0]));
        dp[1][0][0] = even;
        dp[1][0][1] = odd;
        for (let i = 2; i <= n; ++i) {
            for (let j = 0; j <= k; ++j) {
                for (let p = 0; p < 2; ++p) {
                    const cnt = p === 0 ? even : odd;
                    for (let q = 0; q < 2; ++q) {
                        const add = p === q ? 1 : 0;
                        if (j >= add) {
                            dp[i][j][p] = (dp[i][j][p] + dp[i-1][j-add][q] * cnt) % MOD;
                        }
                    }
                }
            }
        }
        return (dp[n][k][0] + dp[n][k][1]) % MOD;
    }
}

Complexity

⏰ Time complexity: O(n * k * 4), since for each position, k, and parity, we check 2 previous parities. This is efficient for the given constraints.
🧺 Space complexity: O(n * k), for the DP table.

Problem#

Examples#

Solution#

Method 1 – Dynamic Programming with Parity Tracking#

Intuition#

Approach#

Code#

Complexity#