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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count the Number of Arrays with K Matching Adjacent Elements

Difficulty: Hard

Problem Description

You are given three integers n, m, k. A good array arr of size n is defined as follows:

  • Each element in arr is in the inclusive range [1, m].
  • Exactly k indices i (where 1 <= i < n) satisfy the condition arr[i - 1] == arr[i].

Return the number of good arrays that can be formed. Since the answer may be very large, return it modulo 10^9 + 7.

Key Insights

  • The problem involves combinatorial counting based on the arrangement of elements and their repetitions.
  • We need to account for the number of ways to choose the positions of the matching elements and the non-matching elements.
  • The transition between matching and non-matching elements can be represented using combinatorial methods.
  • Pre-computation of factorials and modular inverses can help compute combinations efficiently.

Space and Time Complexity

Time Complexity: O(n) for pre-computation and O(1) for each query. Space Complexity: O(n) for storing factorials and inverses.

Solution

To solve this problem, we can use a combinatorial approach. The main idea is to compute:

  1. The total ways to choose k matching pairs from n-1 possible positions.
  2. The arrangements of distinct elements in non-matching positions.
  3. Combine these counts to get the total number of valid arrays.

We will use dynamic programming or combinatorial formulae to compute factorials and their inverses for efficient combination calculations.

Code Solutions

MOD = 10**9 + 7

def countGoodArrays(n, m, k):
    if k > n - 1 or k < 0:
        return 0
    
    # Precompute factorials and inverses
    fact = [1] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], MOD - 2, MOD)  # Fermat's little theorem for inverse
    for i in range(n - 1, 0, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

    # Number of ways to choose positions for k matches
    ways = fact[n - 1] * inv_fact[k] % MOD * inv_fact[n - 1 - k] % MOD
    
    # Each block can be filled in m ways
    total = ways * m * pow(m - 1, n - 1 - k, MOD) % MOD
    
    return total

# Example usage
print(countGoodArrays(3, 2, 1))  # Output: 4
← Back to All Questions