3339. Find the Number of K-Even Arrays - Solution

The 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 10⁹ + 7.

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 <= 750
0 <= k <= n - 1
1 <= m <= 1000

Approach overview

Problem Overview: You need to count how many arrays of length n can be formed from numbers 1..m such that exactly k adjacent pairs have an even sum. Two numbers produce an even sum when they share the same parity (both even or both odd). The task is to count all valid arrays under these constraints.

Approach 1: Memoization Search (Top-Down DP) (Time: O(n * k), Space: O(n * k))

Model the problem using recursion with memoization. Track three values: the current index in the array, how many even-sum adjacent pairs have been formed so far, and the parity of the previous element. At each step, try placing either an even or odd number. If the parity matches the previous element, the pair contributes to the even-sum count. Cache results using a DP table or hash map keyed by (index, evenPairs, prevParity) to avoid recomputation. This turns the exponential brute-force search into a manageable O(n * k) dynamic program.

Approach 2: Bottom-Up Dynamic Programming (Time: O(n * k), Space: O(n * k))

Build the solution iteratively. Let dp[i][j][p] represent the number of ways to construct the first i elements with j even-sum adjacent pairs where the last element has parity p (0 for odd, 1 for even). Transition by adding either parity to the next position. If the new parity matches the previous one, increment the pair counter. Multiply transitions by the number of available values with that parity (count of even numbers vs odd numbers in 1..m). This approach avoids recursion and is easier to reason about during interviews.

The key observation is that the exact values do not matter—only their parity. Precompute how many numbers in 1..m are even and how many are odd. The DP then focuses only on parity transitions, which dramatically reduces the state space.

Recommended for interviews: The bottom-up dynamic programming approach. Start by explaining the parity observation and why adjacent equal parity creates an even sum. Mention that brute force would require exploring m^n arrays, which is infeasible. Transition to a DP state tracking index, pair count, and parity. Interviewers expect this reduction plus careful state transitions, which demonstrates strong DP modeling and familiarity with parity-based counting problems often seen with combinatorics.

Approach 1: Memoization Search

Given the numbers [1, m], there are cnt0 = \lfloor \frac{m}{2} \rfloor even numbers and cnt1 = m - cnt0 odd numbers.

We design a function dfs(i, j, k), which represents the number of ways to fill up to the i-th position, with j remaining positions needing to satisfy the condition, and the parity of the last position being k, where k = 0 indicates the last position is even, and k = 1 indicates the last position is odd. The answer is dfs(0, k, 1).

The execution logic of the function dfs(i, j, k) is as follows:

If j < 0, it means the remaining positions are less than 0, so return 0;
If i \ge n, it means all positions are filled. If j = 0, it means the condition is satisfied, so return 1, otherwise return 0;
Otherwise, we can choose to fill with an odd or even number, calculate the number of ways for both, and return their sum.

The time complexity is O(n times k), and the space complexity is O(n times k). Here, n and k are the parameters given in the problem.

Python

class Solution:
    def countOfArrays(self, n: int, m: int, k: int) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if j < 0:
                return 0
            if i >= n:
                return int(j == 0)
            return (
                cnt1 * dfs(i + 1, j, 1) + cnt0 * dfs(i + 1, j - (k & 1 ^ 1), 0)
            ) % mod

        cnt0 = m // 2
        cnt1 = m - cnt0
        mod = 10**9 + 7
        ans = dfs(0, k, 1)
        dfs.cache_clear()
        return ans

Java

class Solution {
    private Integer[][][] f;
    private long cnt0, cnt1;
    private final int mod = (int) 1e9 + 7;

    public int countOfArrays(int n, int m, int k) {
        f = new Integer[n][k + 1][2];
        cnt0 = m / 2;
        cnt1 = m - cnt0;
        return dfs(0, k, 1);
    }

    private int dfs(int i, int j, int k) {
        if (j < 0) {
            return 0;
        }
        if (i >= f.length) {
            return j == 0 ? 1 : 0;
        }
        if (f[i][j][k] != null) {
            return f[i][j][k];
        }
        int a = (int) (cnt1 * dfs(i + 1, j, 1) % mod);
        int b = (int) (cnt0 * dfs(i + 1, j - (k & 1 ^ 1), 0) % mod);
        return f[i][j][k] = (a + b) % mod;
    }
}

C++

class Solution {
public:
    int countOfArrays(int n, int m, int k) {
        int f[n][k + 1][2];
        memset(f, -1, sizeof(f));
        const int mod = 1e9 + 7;
        int cnt0 = m / 2;
        int cnt1 = m - cnt0;
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
            if (j < 0) {
                return 0;
            }
            if (i >= n) {
                return j == 0 ? 1 : 0;
            }
            if (f[i][j][k] != -1) {
                return f[i][j][k];
            }
            int a = 1LL * cnt1 * dfs(i + 1, j, 1) % mod;
            int b = 1LL * cnt0 * dfs(i + 1, j - (k & 1 ^ 1), 0) % mod;
            return f[i][j][k] = (a + b) % mod;
        };
        return dfs(0, k, 1);
    }
};

TypeScript

function countOfArrays(n: number, m: number, k: number): number {
    const f = Array.from({ length: n }, () =>
        Array.from({ length: k + 1 }, () => Array(2).fill(-1)),
    );
    const mod = 1e9 + 7;
    const cnt0 = Math.floor(m / 2);
    const cnt1 = m - cnt0;
    const dfs = (i: number, j: number, k: number): number => {
        if (j < 0) {
            return 0;
        }
        if (i >= n) {
            return j === 0 ? 1 : 0;
        }
        if (f[i][j][k] !== -1) {
            return f[i][j][k];
        }
        const a = (cnt1 * dfs(i + 1, j, 1)) % mod;
        const b = (cnt0 * dfs(i + 1, j - ((k & 1) ^ 1), 0)) % mod;
        return (f[i][j][k] = (a + b) % mod);
    };
    return dfs(0, k, 1);
}

func countOfArrays(n int, m int, k int) int {
	f := make([][][2]int, n)
	for i := range f {
		f[i] = make([][2]int, k+1)
		for j := range f[i] {
			f[i][j] = [2]int{-1, -1}
		}
	}
	const mod int = 1e9 + 7
	cnt0 := m / 2
	cnt1 := m - cnt0
	var dfs func(int, int, int) int
	dfs = func(i, j, k int) int {
		if j < 0 {
			return 0
		}
		if i >= n {
			if j == 0 {
				return 1
			}
			return 0
		}
		if f[i][j][k] != -1 {
			return f[i][j][k]
		}
		a := cnt1 * dfs(i+1, j, 1) % mod
		b := cnt0 * dfs(i+1, j-(k&1^1), 0) % mod
		f[i][j][k] = (a + b) % mod
		return f[i][j][k]
	}
	return dfs(0, k, 1)
}

Try this approach in the editor

Approach 2: Dynamic Programming

We can convert the memoized search from Solution 1 into dynamic programming.

Define f[i][j][k] to represent the number of ways to fill the i-th position, with j positions satisfying the condition, and the parity of the previous position being k. The answer will be sum_{k = 0}^{1} f[n][k].

Initially, we set f[0][0][1] = 1, indicating that after filling the 0-th position, there are 0 positions satisfying the condition, and the parity of the previous position is odd. All other f[i][j][k] are initialized to 0.

The state transition equations are as follows:

$\begin{aligned} f[i][j][0] &= \left( f[i - 1][j][1] + \left( f[i - 1][j - 1][0] if j > 0 \right) \right) times cnt0 bmod mod, \ f[i][j][1] &= \left( f[i - 1][j][0] + f[i - 1][j][1] \right) times cnt1 bmod mod. \end{aligned}

The time complexity is O(n times k), and the space complexity is O(n times k), where n and k$ are the parameters given in the problem.

Python

class Solution:
    def countOfArrays(self, n: int, m: int, k: int) -> int:
        f = [[[0] * 2 for _ in range(k + 1)] for _ in range(n + 1)]
        cnt0 = m // 2
        cnt1 = m - cnt0
        mod = 10**9 + 7
        f[0][0][1] = 1
        for i in range(1, n + 1):
            for j in range(k + 1):
                f[i][j][0] = (
                    (f[i - 1][j][1] + (f[i - 1][j - 1][0] if j else 0)) * cnt0 % mod
                )
                f[i][j][1] = (f[i - 1][j][0] + f[i - 1][j][1]) * cnt1 % mod
        return sum(f[n][k]) % mod

Java

class Solution {
    public int countOfArrays(int n, int m, int k) {
        int[][][] f = new int[n + 1][k + 1][2];
        int cnt0 = m / 2;
        int cnt1 = m - cnt0;
        final int mod = (int) 1e9 + 7;
        f[0][0][1] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                f[i][j][0]
                    = (int) (1L * cnt0 * (f[i - 1][j][1] + (j > 0 ? f[i - 1][j - 1][0] : 0)) % mod);
                f[i][j][1] = (int) (1L * cnt1 * (f[i - 1][j][0] + f[i - 1][j][1]) % mod);
            }
        }
        return (f[n][k][0] + f[n][k][1]) % mod;
    }
}

C++

class Solution {
public:
    int countOfArrays(int n, int m, int k) {
        int f[n + 1][k + 1][2];
        memset(f, 0, sizeof(f));
        f[0][0][1] = 1;
        const int mod = 1e9 + 7;
        int cnt0 = m / 2;
        int cnt1 = m - cnt0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                f[i][j][0] = 1LL * (f[i - 1][j][1] + (j ? f[i - 1][j - 1][0] : 0)) * cnt0 % mod;
                f[i][j][1] = 1LL * (f[i - 1][j][0] + f[i - 1][j][1]) * cnt1 % mod;
            }
        }
        return (f[n][k][0] + f[n][k][1]) % mod;
    }
};

TypeScript

function countOfArrays(n: number, m: number, k: number): number {
    const f: number[][][] = Array.from({ length: n + 1 }, () =>
        Array.from({ length: k + 1 }, () => Array(2).fill(0)),
    );
    f[0][0][1] = 1;
    const mod = 1e9 + 7;
    const cnt0 = Math.floor(m / 2);
    const cnt1 = m - cnt0;
    for (let i = 1; i <= n; ++i) {
        for (let j = 0; j <= k; ++j) {
            f[i][j][0] = (cnt0 * (f[i - 1][j][1] + (j ? f[i - 1][j - 1][0] : 0))) % mod;
            f[i][j][1] = (cnt1 * (f[i - 1][j][0] + f[i - 1][j][1])) % mod;
        }
    }
    return (f[n][k][0] + f[n][k][1]) % mod;
}

func countOfArrays(n int, m int, k int) int {
	f := make([][][2]int, n+1)
	for i := range f {
		f[i] = make([][2]int, k+1)
	}
	f[0][0][1] = 1
	cnt0 := m / 2
	cnt1 := m - cnt0
	const mod int = 1e9 + 7
	for i := 1; i <= n; i++ {
		for j := 0; j <= k; j++ {
			f[i][j][0] = cnt0 * f[i-1][j][1] % mod
			if j > 0 {
				f[i][j][0] = (f[i][j][0] + cnt0*f[i-1][j-1][0]%mod) % mod
			}
			f[i][j][1] = cnt1 * (f[i-1][j][0] + f[i-1][j][1]) % mod
		}
	}
	return (f[n][k][0] + f[n][k][1]) % mod
}

Try this approach in the editor

Approach 3: Dynamic Programming (Space Optimization)

We observe that the computation of f[i] only depends on f[i - 1], allowing us to optimize the space usage with a rolling array.

The time complexity is O(n times k), and the space complexity is O(k), where n and k are the parameters given in the problem.

Python

class Solution:
    def countOfArrays(self, n: int, m: int, k: int) -> int:
        f = [[0] * 2 for _ in range(k + 1)]
        cnt0 = m // 2
        cnt1 = m - cnt0
        mod = 10**9 + 7
        f[0][1] = 1
        for _ in range(n):
            g = [[0] * 2 for _ in range(k + 1)]
            for j in range(k + 1):
                g[j][0] = (f[j][1] + (f[j - 1][0] if j else 0)) * cnt0 % mod
                g[j][1] = (f[j][0] + f[j][1]) * cnt1 % mod
            f = g
        return sum(f[k]) % mod

Java

class Solution {
    public int countOfArrays(int n, int m, int k) {
        int[][] f = new int[k + 1][2];
        int cnt0 = m / 2;
        int cnt1 = m - cnt0;
        final int mod = (int) 1e9 + 7;
        f[0][1] = 1;
        for (int i = 0; i < n; ++i) {
            int[][] g = new int[k + 1][2];
            for (int j = 0; j <= k; ++j) {
                g[j][0] = (int) (1L * cnt0 * (f[j][1] + (j > 0 ? f[j - 1][0] : 0)) % mod);
                g[j][1] = (int) (1L * cnt1 * (f[j][0] + f[j][1]) % mod);
            }
            f = g;
        }
        return (f[k][0] + f[k][1]) % mod;
    }
}

C++

class Solution {
public:
    int countOfArrays(int n, int m, int k) {
        vector<vector<int>> f(k + 1, vector<int>(2));
        int cnt0 = m / 2;
        int cnt1 = m - cnt0;
        const int mod = 1e9 + 7;
        f[0][1] = 1;

        for (int i = 0; i < n; ++i) {
            vector<vector<int>> g(k + 1, vector<int>(2));
            for (int j = 0; j <= k; ++j) {
                g[j][0] = (1LL * cnt0 * (f[j][1] + (j > 0 ? f[j - 1][0] : 0)) % mod) % mod;
                g[j][1] = (1LL * cnt1 * (f[j][0] + f[j][1]) % mod) % mod;
            }
            f = g;
        }
        return (f[k][0] + f[k][1]) % mod;
    }
};

TypeScript

function countOfArrays(n: number, m: number, k: number): number {
    const mod = 1e9 + 7;
    const cnt0 = Math.floor(m / 2);
    const cnt1 = m - cnt0;
    const f: number[][] = Array.from({ length: k + 1 }, () => [0, 0]);
    f[0][1] = 1;
    for (let i = 0; i < n; i++) {
        const g: number[][] = Array.from({ length: k + 1 }, () => [0, 0]);
        for (let j = 0; j <= k; j++) {
            g[j][0] = ((cnt0 * (f[j][1] + (j > 0 ? f[j - 1][0] : 0))) % mod) % mod;
            g[j][1] = ((cnt1 * (f[j][0] + f[j][1])) % mod) % mod;
        }
        f.splice(0, f.length, ...g);
    }
    return (f[k][0] + f[k][1]) % mod;
}

func countOfArrays(n int, m int, k int) int {
	const mod = 1e9 + 7
	cnt0 := m / 2
	cnt1 := m - cnt0
	f := make([][2]int, k+1)
	f[0][1] = 1

	for i := 0; i < n; i++ {
		g := make([][2]int, k+1)
		for j := 0; j <= k; j++ {
			g[j][0] = (cnt0 * (f[j][1] + func() int {
				if j > 0 {
					return f[j-1][0]
				}
				return 0
			}()) % mod) % mod
			g[j][1] = (cnt1 * (f[j][0] + f[j][1]) % mod) % mod
		}
		f = g
	}

	return (f[k][0] + f[k][1]) % mod
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Memoization Search	–
Dynamic Programming	–
Dynamic Programming (Space Optimization)	–

Complexity analysis

Approach	Time	Space	When to Use
Memoization Search (Top-Down DP)	O(n * k)	O(n * k)	Useful when reasoning recursively about choices and parity transitions.
Bottom-Up Dynamic Programming	O(n * k)	O(n * k)	Preferred in interviews and production due to iterative state transitions and predictable memory usage.

Frequently asked questions

Is Find the Number of K-Even Arrays easy or hard?

The problem is generally considered Medium difficulty. The challenge is recognizing that only parity matters and modeling the state correctly with dynamic programming to track adjacent pair contributions.

Find the Number of K-Even Arrays Python/Java solution

Both Python and Java implementations follow the same DP logic: compute counts of even and odd numbers in 1..m, maintain a DP table for states (index, pairCount, parity), and iterate or recurse with memoization to accumulate valid arrays.

How to solve Find the Number of K-Even Arrays in O(n * k)?

Count how many numbers in 1..m are even and odd. Use a DP state like dp[i][j][p] representing the number of arrays of length i with j even-sum adjacent pairs and last parity p. Transition by adding an even or odd value and update the pair count when the parity matches the previous element.

What is the best approach for Find the Number of K-Even Arrays?

Dynamic programming based on parity transitions is the most efficient approach. Track the array length processed, the number of even-sum adjacent pairs formed, and the parity of the last element. This reduces the search space from m^n possibilities to O(n * k) states and computes the answer efficiently.

Is Find the Number of K-Even Arrays asked at Google/Amazon/Meta?

Problems that require counting arrays with parity constraints and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. The exact problem may vary, but the DP modeling pattern is commonly tested.

What data structure is used in Find the Number of K-Even Arrays?

The core structure is a dynamic programming table or memoization cache. The state typically tracks index, number of valid adjacent pairs formed, and parity of the last element.

What is the time complexity of Find the Number of K-Even Arrays?

The optimal dynamic programming solution runs in O(n * k) time. Each state represents a position in the array and a count of even-sum adjacent pairs, with only two parity transitions (even or odd) per step.

Find the Number of K-Even Arrays solution and explanation

The problem

Approach overview

Approach 1: Memoization Search

Approach 2: Dynamic Programming

Approach 3: Dynamic Programming (Space Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Number of K-Even Arrays solution and explanation

The problem

Approach overview

Approach 1: Memoization Search

Approach 2: Dynamic Programming

Approach 3: Dynamic Programming (Space Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems