Skip to main content
Talentd

Find the Number of K-Even Arrays - Solution & Explanation

MediumPremiumFree on FleetCodeDynamic Programming21 min read
Practice this problem

Problem Statement

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 <= 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Memoization Search—
Dynamic Programming—
Dynamic Programming (Space Optimization)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 ProgrammingO(n * k)O(n * k)Preferred in interviews and production due to iterative state transitions and predictable memory usage.

Video Solution

Top K Frequent Elements - Bucket Sort - Leetcode 347 - Python • NeetCode • 665,789 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find the Number of K-Even Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sort Array By Parity II