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.
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 <= 1000Problem 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.
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:
j < 0, it means the remaining positions are less than 0, so return 0;i \ge n, it means all positions are filled. If j = 0, it means the condition is satisfied, so return 1, otherwise return 0;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
Java
C++
Go
TypeScript
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
Java
C++
Go
TypeScript
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
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Memoization Search | — |
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
| 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. |
Top K Frequent Elements - Bucket Sort - Leetcode 347 - Python • NeetCode • 665,789 views views
Watch 9 more video solutions →Practice Find the Number of K-Even Arrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor