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.

Description Hints 2 Solution Video 8:34

3339. Find the Number of K-Even Arrays

Medium61.3% acceptancePremium elsewhere, free here

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

Topics

Dynamic Programming

Hints open one at a time

Hint 1

Use dynamic programming.

Hint 2

Store whether the last element was even or odd.

8:34

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

3339. Find the Number of K-Even Arrays

Topics

Hints open one at a time

Similar problems