You are given three integers n, m, k. A good array arr of size n is defined as follows:…
- User
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.
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. 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. 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.
Constraints:
1 <= n <= 10^5 1 <= m <= 10^5 0 <= k <= n - 1
Complete the below C++ code - class Solution { public: int countGoodArrays(int n, int m, int k) {
}};
- Assistant
To solve the problem of counting "good arrays," we need to understand the constraints and how to approach the problem combinatorially.
Problem Breakdown
-
Definition of a Good Array:
- Each element is within the range
[1, m]. - Exactly
kindices satisfyarr[i - 1] == arr[i].
- Each element is within the range
-
Combinatorial Insight:
- We can represent the array as sequences of "runs" where a run is a maximal sequence of equal elements.
- If there are exactly
kequal consecutive pairs, then the number of runsrin the array isr = n - k. - For each run:
- The first run can be any of the
melements. - Each subsequent run must be different from the previous run, giving
m-1choices for each.
- The first run can be any of the
-
Mathematical Formula:
- The number of ways to partition the array into
r = n - kruns is given by the binomial coefficientC(n-1, k)(choosingkpositions out ofn-1to have equal consecutive pairs). - The total number of good arrays can be computed as: [ \text{Total ways} = C(n-1, k) \times m \times (m-1)^{n-k-1} \mod 10^9 + 7 ]
- The number of ways to partition the array into
-
Implementation Steps:
- Precompute factorials and their modular inverses to efficiently calculate binomial coefficients.
- Use fast exponentiation to compute powers efficiently.
- Handle edge cases where
n = 1orkis out of valid bounds.
Final C++ Implementation
#include <bits/stdc++.h> using namespace std; typedef long long ll; class Solution { public: const int mod = 1'000'000'007; // Function to compute a^b mod mod ll power_mod(ll a, ll b, ll mod_val){ ll res = 1; a %= mod_val; while(b > 0){ if(b & 1){ res = res * a % mod_val; } a = a * a % mod_val; b >>= 1; } return res; } int countGoodArrays(int n, int m, int k) { // Edge case when n ==1 if(n ==1){ if(k ==0) return m; else return 0; } // If k > n-1 or k <0, no such arrays if(k > n-1 || k <0) return 0; // Precompute factorial and inv factorial up to n-1 // Since n <=1e5, it's manageable vector<long long> fact(n, 1); for(int i=1;i<n;i++) fact[i] = fact[i-1] * i % mod; // Compute inv_fact[n-1] using Fermat's little theorem vector<long long> inv_fact(n, 1); inv_fact[n-1] = power_mod(fact[n-1], mod-2, mod); for(int i=n-2;i>=0;i--){ inv_fact[i] = inv_fact[i+1] * (i+1) % mod; } // Compute C(n-1, k) ll C; if(k ==0){ C = 1; } else{ C = fact[n-1] * inv_fact[k] % mod; C = C * inv_fact[n-1 -k] % mod; } // Compute (m-1)^(n -k -1) // When n -k -1 ==0, it's 1 ll power_val; if(n -k -1 >=0){ power_val = power_mod(m-1, n -k -1, mod); } else{ power_val = 1; // Should not occur as k <=n-1 } // Calculate m * (m-1)^(n -k -1) % mod ll mult = m * power_val % mod; // Final answer: C * mult % mod ll res = C * mult % mod; return (int)res; } };Explanation of the Code
-
Power Function: Implements fast exponentiation to compute ( (m-1)^{n-k-1} ) efficiently under modulo ( 10^9 + 7 ).
-
Factorial and Inverse Factorial:
- Precomputes the factorial values and their modular inverses up to
n-1to facilitate quick computation of binomial coefficients.
- Precomputes the factorial values and their modular inverses up to
-
Binomial Coefficient: Calculates ( C(n-1, k) ) using the precomputed factorials and inverse factorials.
-
Final Calculation: Multiplies the binomial coefficient with
mand ( (m-1)^{n-k-1} ), ensuring all operations are performed under the modulo to prevent overflow.
Validation with Examples
The implementation matches the given examples:
- Example 1:
n = 3, m = 2, k = 1yields4. - Example 2:
n = 4, m = 2, k = 2yields6. - Example 3:
n = 5, m = 2, k = 0yields2.
Conclusion
This solution efficiently computes the number of good arrays using combinatorial mathematics and modular arithmetic, ensuring it operates within the given constraints.
-