We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Number of K-Even Arrays

Number: 3614

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given integers n, m, and k, count the number of arrays arr of size n (with each element from 1 to m) that are called k-even. An array is k-even if exactly k indices i (0 ≤ i < n - 1) satisfy that (arr[i] * arr[i+1]) - arr[i] - arr[i+1] is even. Return the answer modulo 10^9 + 7.

Key Insights

  • The expression (a * b) - a - b simplifies algebraically to (a-1)*(b-1) - 1.
  • Analyzing the parity, the expression is even if and only if both a and b are even.
  • Count the number of evens (e) and odds (o) in [1, m]. Then the problem reduces to counting arrays with exactly k occurrences where two consecutive elements are even.
  • A dynamic programming (DP) approach can track the number of arrays built so far along with the last element’s parity.

Space and Time Complexity

Time Complexity: O(n * k)
Space Complexity: O(n * k) [can be optimized to O(k)]

Solution

We use DP with state dp[i][j][p] where:

  • i is the current length of the array.
  • j is the number of pairs of consecutive even numbers seen so far.
  • p indicates the parity of the last element (0 for odd, 1 for even).

Initialization:

  • For the first element, dp[1][0][0] = o (number of odds) and dp[1][0][1] = e (number of evens).

Transitions:

  1. When adding an odd number:
    • The parity does not contribute a new even-even pair.
    • dp[i][j][0] += (dp[i-1][j][0] + dp[i-1][j][1]) * o.
  2. When adding an even number:
    • If the previous number was even, it forms an even-even pair. Thus, dp[i][j][1] gets contribution from dp[i-1][j-1][1] * e.
    • If the previous number was odd, no new even-even pair is added so: dp[i][j][1] += dp[i-1][j][0] * e.

The final answer is the sum dp[n][k][0] + dp[n][k][1] modulo 10^9+7.

Code Solutions

# Python solution using dynamic programming

MOD = 10**9 + 7

def countKEvenArrays(n, m, k):
    # Count evens and odds in range [1, m]
    even_count = m // 2
    odd_count = m - even_count
    
    # Initialize dp table: dp[i][j][p] where p: 0 for odd, 1 for even
    dp = [[[0, 0] for _ in range(k+1)] for _ in range(n+1)]
    
    # Base case for first element
    dp[1][0][0] = odd_count  # ending with odd
    dp[1][0][1] = even_count  # ending with even
    
    # Fill dp for the rest of positions 2..n
    for i in range(2, n+1):
        for j in range(0, k+1):
            # If we end with an odd number
            dp[i][j][0] = ((dp[i-1][j][0] + dp[i-1][j][1]) * odd_count) % MOD
            # If we end with an even number from a previous odd: no new pair
            dp[i][j][1] = (dp[i-1][j][0] * even_count) % MOD
            # If we end with an even number from a previous even: new pair added
            if j > 0:
                dp[i][j][1] = (dp[i][j][1] + dp[i-1][j-1][1] * even_count) % MOD
    return (dp[n][k][0] + dp[n][k][1]) % MOD

# Example test cases:
print(countKEvenArrays(3, 4, 2))  # Expected output 8 
print(countKEvenArrays(5, 1, 0))  # Expected output 1
print(countKEvenArrays(7, 7, 5))  # Expected output 5832
← Back to All Questions