1922. Count Good Numbers

Time: O(log n)

Space: O(1)

Approach

Fast power for count of even-position choices (5 options) and odd-position choices (4 options).

Key Techniques

Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.

Counting

Counting problems enumerate valid configurations without explicitly generating them. Techniques: combinatorics (nCr), inclusion-exclusion, digit DP, and contribution of each element. In C#, use long to avoid overflow when multiplying counts.

1922.cs

// Approach: Fast power for count of even-position choices (5 options) and odd-position choices (4 options).
// Time: O(log n) Space: O(1)

public class Solution
{
    int mod = 1000000007;
    public int CountGoodNumbers(long n)
    {
        long countOfFour = (n / 2);
        long countOfFive = (n / 2) + (n % 2);
        return (int)(GoodNumbersCount(5, countOfFive) % mod * GoodNumbersCount(4, countOfFour) % mod) % mod;
    }

    private long GoodNumbersCount(long i, long n)
    {
        if (n == 0)
            return 1;

        if (n % 2 == 0)
            return GoodNumbersCount((i % mod * i % mod) % mod, n / 2);
        else
            return (i % mod * GoodNumbersCount(i % mod, n - 1) % mod) % mod;
    }
}

Was this solution helpful?