3405. Count the Number of Arrays with K Matching Adjacent Elements
Difficulty: Hard
Topics: Math
, Combinatorics
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 theinclusive
range[1, m]
. -
Exactly
k
indicesi
(where1 <= i < n
) satisfy the conditionarr[i - 1] == arr[i]
.
Return the number of good arrays that can be formed.
Since the answer may be very large, return it modulo 109 + 7
.
Example 1:
- Input: n = 3, m = 2, k = 1
- Output: 4
-
Explanation:
- There are 4 good arrays. They are
[1, 1, 2]
,[1, 2, 2]
,[2, 1, 1]
and[2, 2, 1]
. - Hence, the answer is 4.
- There are 4 good arrays. They are
Example 2:
- Input: n = 4, m = 2, k = 2
- Output: 6
-
Explanation:
- The good arrays are
[1, 1, 1, 2]
,[1, 1, 2, 2]
,[1, 2, 2, 2]
,[2, 1, 1, 1]
,[2, 2, 1, 1]
and[2, 2, 2, 1]
. - Hence, the answer is 6.
- The good arrays are
Example 3:
- Input: n = 5, m = 2, k = 0
- Output: 2
-
Explanation:
- The good arrays are
[1, 2, 1, 2, 1]
and[2, 1, 2, 1, 2]
. - Hence, the answer is 2.
- The good arrays are
Constraints:
1 <= n <= 105
1 <= m <= 105
0 <= k <= n - 1
Hint:
- The first position
arr[0]
hasm
choices. - For each of the remaining
n - 1
indices,0 < i < n
, selectk
positions from left to right and setarr[i] = arr[i - 1]
. - For all other indices, set
arr[i] != arr[i - 1]
with (m - 1
) choices for each of then - 1 - k
positions.
Solution:
We need to count the number of “good arrays” of size n
where each element is in the range [1, m]
and exactly k
adjacent elements are equal. The solution involves combinatorial mathematics and modular arithmetic to efficiently compute the result, especially given the constraints where n
and m
can be as large as 105.
Approach
-
Problem Analysis: The problem requires constructing arrays of length
n
with elements from1
tom
such that exactlyk
adjacent pairs (i.e.,arr[i-1] == arr[i]
) exist. The solution leverages combinatorial mathematics to determine the number of valid arrays:-
Initial Element: The first element of the array can be any of the
m
choices. -
Adjacent Pairs: Among the
n-1
adjacent pairs, we need to choosek
positions where the elements are equal. The number of ways to choose these positions is given by the binomial coefficient C(n-1, k). -
Non-adjacent Pairs: For the remaining
n-1-k
positions, the elements must differ from their immediate predecessors. Each such position offersm-1
choices (any value except the previous element).
-
Initial Element: The first element of the array can be any of the
-
Combinatorial Formula: The total number of good arrays is calculated as:
result = m × C(n-1, k) × (m-1)(n-1-k)
Here, C(n-1, k) is the binomial coefficient representing the number of ways to choose k
positions out of n-1
for equal adjacent pairs.
-
Modular Arithmetic: Given the large constraints, all calculations are performed modulo 109 + 7 to avoid overflow and meet the problem requirements.
-
Efficient Computation:
- Factorial Precomputation: Precompute factorials up to n-1 to efficiently compute binomial coefficients using modular inverses (via Fermat’s Little Theorem).
- Fast Exponentiation: Compute (m-1)(n-1-k) efficiently using modular exponentiation (power by squaring).
Let’s implement this solution in PHP: 3405. Count the Number of Arrays with K Matching Adjacent Elements
<?php
/**
* @param Integer $n
* @param Integer $m
* @param Integer $k
* @return Integer
*/
function countGoodArrays($n, $m, $k) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* Modular exponentiation
*
* @param $base
* @param $exponent
* @param $mod
* @return int
*/
function mod_pow($base, $exponent, $mod) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example usage:
echo countGoodArrays(3, 2, 1) . "n"; // Output: 4
echo countGoodArrays(4, 2, 2) . "n"; // Output: 6
echo countGoodArrays(5, 2, 0) . "n"; // Output: 2
?>
Explanation:
-
Initial Checks: If
k
exceeds the number of adjacent pairs (n-1
), return 0 since it’s impossible to have more equal pairs than available positions. -
Factorial Precomputation: Precompute factorials up to
n-1
modulo 109 + 7 to facilitate binomial coefficient calculations. - Binomial Coefficient Calculation: Compute C(n-1, k) using factorials and modular inverses (using Fermat’s Little Theorem for efficiency).
- Exponentiation: Calculate (m-1)(n-1-k) using fast exponentiation to handle large powers efficiently under modulo.
- Result Calculation: Combine the results (initial element choices, binomial coefficient, and the exponentiation result) under modulo 109 + 7 to get the final count of good arrays.
This approach efficiently combines combinatorial mathematics with modular arithmetic to solve the problem within feasible computational limits, even for large inputs.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me: