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

Count the Number of Arrays with K Matching Adjacent Elements

Number: 3682

Difficulty: Hard

Paid? No

Companies: Bloomberg

Problem Description

You are given three integers n, m, and k. A good array arr of size n is such that:

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

Return the number of good arrays that can be formed modulo (10^9 + 7).

Key Insights

  • The array can be viewed as being divided into segments; equal adjacent pairs occur inside a segment.
  • If there are exactly k adjacent equal pairs in an array of n numbers, then the array forms (n - k) segments.
  • The first element of the array can be chosen in m ways.
  • Whenever a new segment begins, the number must change; hence there are (m - 1) choices for each new segment (after the first).
  • The positions (in the n-1 gaps) where the segment breaks occur can be chosen in C(n-1, k) ways.
  • The final formula becomes: result = m * (m - 1)^(n - 1 - k) * C(n - 1, k) mod (10^9+7).

Space and Time Complexity

Time Complexity: O(n) where n is up to 10^5 (main work is precomputing factorials and modular inverses). Space Complexity: O(n) for storing the factorials and inverse factorials arrays.

Solution

The core idea is to count the number of ways to partition the array into segments. With exactly k adjacent equal pairs, the array is split into (n - k) segments. The first element is free with m choices, and for each new segment (from the remaining (n-k-1) segments), we must choose a number different from the previous value, giving (m-1) choices each. In addition, we have to choose which k of the n-1 adjacent pairs are “equal” pairs (i.e. do not cause a new segment start). This is given by C(n-1, k). Multiplying these together gives:

  result = m * (m - 1)^(n - 1 - k) * C(n-1, k) modulo (10^9+7).

This uses combinatorics, fast modular exponentiation, and factorial precomputation (with modular inverses) to compute the binomial coefficient C(n-1, k) efficiently.

Code Solutions

MOD = 10**9 + 7

def mod_exp(base, exponent, mod):
    # Fast modular exponentiation
    result = 1
    base %= mod
    while exponent:
        if exponent & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exponent //= 2
    return result

def precompute_factorials(n, mod):
    # Precompute factorials and inverse factorials up to n.
    fact = [1] * (n + 1)
    inv_fact = [1] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = fact[i-1] * i % mod
    inv_fact[n] = mod_exp(fact[n], mod - 2, mod)  # Fermat's little theorem
    for i in range(n - 1, 0, -1):
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % mod
    return fact, inv_fact

def nCr(n, r, fact, inv_fact, mod):
    if r < 0 or r > n:
        return 0
    return (fact[n] * inv_fact[r] % mod) * inv_fact[n - r] % mod

def countGoodArrays(n, m, k):
    # We need factorials up to n-1
    fact, inv_fact = precompute_factorials(n - 1, MOD)
    ways_to_choose_matches = nCr(n - 1, k, fact, inv_fact, MOD)
    segments = n - k - 1  # There are (n - k - 1) transitions that are forced to be different after the first element.
    ways_to_choose_segments = mod_exp(m - 1, segments, MOD)
    # The first element can be chosen in m ways.
    result = (m * ways_to_choose_segments % MOD) * ways_to_choose_matches % MOD
    return result

# Example test cases
print(countGoodArrays(3, 2, 1))  # Expected output 4
print(countGoodArrays(4, 2, 2))  # Expected output 6
print(countGoodArrays(5, 2, 0))  # Expected output 2
← Back to All Questions