Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

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

  1. 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) {

    }
    

    };

  2. Assistant

    To solve the problem of counting "good arrays," we need to understand the constraints and how to approach the problem combinatorially.

    Problem Breakdown

    1. Definition of a Good Array:

      • Each element is within the range [1, m].
      • Exactly k indices satisfy arr[i - 1] == arr[i].
    2. 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 k equal consecutive pairs, then the number of runs r in the array is r = n - k.
      • For each run:
        • The first run can be any of the m elements.
        • Each subsequent run must be different from the previous run, giving m-1 choices for each.
    3. Mathematical Formula:

      • The number of ways to partition the array into r = n - k runs is given by the binomial coefficient C(n-1, k) (choosing k positions out of n-1 to 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 ]
    4. 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 = 1 or k is 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

    1. Power Function: Implements fast exponentiation to compute ( (m-1)^{n-k-1} ) efficiently under modulo ( 10^9 + 7 ).

    2. Factorial and Inverse Factorial:

      • Precomputes the factorial values and their modular inverses up to n-1 to facilitate quick computation of binomial coefficients.
    3. Binomial Coefficient: Calculates ( C(n-1, k) ) using the precomputed factorials and inverse factorials.

    4. Final Calculation: Multiplies the binomial coefficient with m and ( (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 = 1 yields 4.
    • Example 2: n = 4, m = 2, k = 2 yields 6.
    • Example 3: n = 5, m = 2, k = 0 yields 2.

    Conclusion

    This solution efficiently computes the number of good arrays using combinatorial mathematics and modular arithmetic, ensuring it operates within the given constraints.