πΉ Problem: 3405. Count the Number of Arrays with K Matching Adjacent Elements
Difficulty: Hard
Tags: #Combinatorics, #Math, #DP
π Problem Summary
We are given three integers
n
,m
, andk
. We must count how many arrays of lengthn
we can build such that:
- Every element is from the range
[1, m]
.- Exactly
k
adjacent index pairs (i.e.,arr[i-1] == arr[i]
) must be equal. No index can be part of more than one such pair, and the total result must be returned modulo 10βΉ+7.
π§ My Thought Process
Brute Force Idea:
Honestly, my brute force was more like "brute cluelessness." π΅
I thought: "Okay... just try all possible arrays and check if they satisfy the condition," but with constraints up to 10β΅, this is 100% dead on arrival.Optimized Strategy:
Enter: π§ββοΈ The Great ChatGPT and his sacred scrolls of combinatorics!
Hereβs how the optimized solution works:
Choose
k
positions (out ofn-1
adjacent pairs) where elements will be the same.
This can be done inC(n-1, k)
ways.Choose the first element of the array in
m
ways.For the remaining
n - 1 - k
positions, you must pick a different value than the previous β so for each of these, you havem - 1
choices.
Final formula:
ways = C(n - 1, k) * m * (m - 1)^(n - 1 - k)
-
Algorithm Used:
Modular Combinatorics
,Fast Exponentiation
,Math
βοΈ Code Implementation (Python)
MOD = 10**9 + 7
MAX = 10**5 + 10 # Safety margin for n up to 1e5
# Precompute factorials and inverse factorials
fact = [1] * MAX
inv_fact = [1] * MAX
for i in range(1, MAX):
fact[i] = fact[i - 1] * i % MOD
# Inverse of factorial using Fermat's Little Theorem
inv_fact[MAX - 1] = pow(fact[MAX - 1], MOD - 2, MOD)
for i in range(MAX - 2, -1, -1):
inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
def comb_mod(n, k):
if k < 0 or k > n:
return 0
return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD
class Solution:
def countGoodArrays(self, n: int, m: int, k: int) -> int:
return comb_mod(n - 1, k) * m % MOD * pow(m - 1, n - 1 - k, MOD) % MOD
β±οΈ Time & Space Complexity
- Time: O(n) for precomputing factorials and inverse using built-ins
- Space: O(1) if using Pythonβs built-in factorials (else O(n) if you precompute them)
π§© Key Takeaways
- β
Learned how to count combinations modulo a prime using
math.factorial
+ modular inverse. - π‘ The trickiest part was understanding the separation of adjacent equal-pair placements from distinct ones.
- π If a problem says βexactly K adjacent matches,β chances are, it's asking for clever combinatorics, not brute force.
π Reflection (Self-Check)
- [x] Could I solve this without help? β Nope, needed help.
- [ ] Did I write code from scratch? β Partially, modified a solution I found.
- [x] Did I understand why it works? β Yes, after breaking it down.
- [x] Will I be able to recall this in a week? β Yes, especially with the pattern in mind.
π Related Problems
- 935. Knight Dialer
- 628. Maximum Product of Three Numbers
- 1866. Number of Ways to Rearrange Sticks With K Sticks Visible
π Progress Tracker
Metric | Value |
---|---|
Day | 22 |
Total Problems Solved | 354 |
Confidence Today | π |
Top comments (0)