Find the Number of K-Even Arrays - Video Solutions

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.