Find the Number of K-Even Arrays
MediumUpdated: Aug 2, 2025
Practice on:
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:
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:
Input: n = 5, m = 1, k = 0
Output: 1
Explanation:
The only 0-even array is `[1, 1, 1, 1, 1]`.
Example 3:
Input: n = 7, m = 7, k = 5
Output: 5832
Constraints:
1 <= n <= 7500 <= k <= n - 11 <= 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
oddbe the count of odd numbers in[1, m], andevenbe the count of even numbers in[1, m]. - Define
dp[i][j][p]as the number of arrays of lengthi, withjk-even pairs, ending with parityp(0for even,1for odd). - Initialize
dp[1][0][0] = even,dp[1][0][1] = odd. - For each position
ifrom 2 ton, for eachjfrom 0 tok, and for each parityp:- If the previous parity is the same as
p, incrementj(since the pair is k-even). - Otherwise,
jstays the same. - Transition:
dp[i][j][p] += dp[i-1][j-(p==q)][q] * (even if p==0 else odd)forqin{0,1}.
- If the previous parity is the same as
- The answer is
dp[n][k][0] + dp[n][k][1]modulo10**9 + 7.
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Kotlin
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
}
}
Python
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
Rust
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
}
}
TypeScript
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.