2025-06-17 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's June LeetCoding Challenge with cpp.

June LeetCoding Challenge 17

Description

Count the Number of Arrays with K Matching Adjacent Elements

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 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.

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 <= 105
  • 1 <= m <= 105
  • 0 <= k <= n - 1

Solution

const int MOD = 1e9 + 7;
const int MMAX = 1e5 + 1;

long long fact[MMAX] = {};
long long invFact[MMAX] = {};
long long qpow(long long base, int exp) {
  long long result = 1;
  while (exp) {
    if (exp & 1) {
      result *= base;
      result %= MOD;
    }
    base *= base;
    base %= MOD;
    exp >>= 1;
  }
  return result;
}

long long combination(int n, int m) {
  return fact[n] * invFact[m] % MOD * invFact[n - m] % MOD;
}
auto _ = [](){
  fact[0] = 1;
  for (int i = 1; i < MMAX; i++) {
    fact[i] = fact[i - 1] * i % MOD;
  }

  invFact[MMAX - 1] = qpow(fact[MMAX - 1], MOD - 2);
  for (int i = MMAX - 1; i; i--) {
    invFact[i - 1] = invFact[i] * i % MOD;
  }
  return 2;
}();
class Solution {
public:
  int countGoodArrays(int n, int m, int k) {
    return combination(n - 1, k) * m % MOD * qpow(m - 1, n - 1 - k) % MOD;
  }
};

// Accepted
// 809/809 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 79.55 % of cpp submissions (9.9 MB)
Algorithm