Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1922. Count Good Numbers - Leetcode Solution

Code Implementation

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10**9 + 7

        def mod_pow(a, b):
            result = 1
            a = a % MOD
            while b > 0:
                if b % 2 == 1:
                    result = (result * a) % MOD
                a = (a * a) % MOD
                b //= 2
            return result

        even_positions = (n + 1) // 2
        odd_positions = n // 2
        return (mod_pow(5, even_positions) * mod_pow(4, odd_positions)) % MOD
      
class Solution {
public:
    static constexpr int MOD = 1e9 + 7;

    long long mod_pow(long long a, long long b) {
        long long result = 1;
        a %= MOD;
        while (b > 0) {
            if (b % 2 == 1)
                result = (result * a) % MOD;
            a = (a * a) % MOD;
            b /= 2;
        }
        return result;
    }

    int countGoodNumbers(long long n) {
        long long even_positions = (n + 1) / 2;
        long long odd_positions = n / 2;
        return (int)((mod_pow(5, even_positions) * mod_pow(4, odd_positions)) % MOD);
    }
};
      
class Solution {
    static final int MOD = 1_000_000_007;

    private long modPow(long a, long b) {
        long result = 1;
        a %= MOD;
        while (b > 0) {
            if (b % 2 == 1) result = (result * a) % MOD;
            a = (a * a) % MOD;
            b /= 2;
        }
        return result;
    }

    public int countGoodNumbers(long n) {
        long evenPositions = (n + 1) / 2;
        long oddPositions = n / 2;
        long res = (modPow(5, evenPositions) * modPow(4, oddPositions)) % MOD;
        return (int) res;
    }
}
      
var countGoodNumbers = function(n) {
    const MOD = 1e9 + 7;

    function modPow(a, b) {
        let result = 1n;
        a = BigInt(a % MOD);
        b = BigInt(b);
        let mod = BigInt(MOD);
        while (b > 0) {
            if (b % 2n === 1n) result = (result * a) % mod;
            a = (a * a) % mod;
            b = b / 2n;
        }
        return result;
    }

    let evenPositions = Math.floor((n + 1) / 2);
    let oddPositions = Math.floor(n / 2);
    let res = (modPow(5, evenPositions) * modPow(4, oddPositions)) % BigInt(MOD);
    return Number(res);
};

Problem Description

Given an integer n, a "good" number is defined as a digit string of length n where:
  • Digits at even indices (0-based) are even (i.e., one of 0, 2, 4, 6, 8).
  • Digits at odd indices are prime digits (i.e., one of 2, 3, 5, 7).
Return the total number of good digit strings of length n, modulo 10^9 + 7.

Key Constraints:
  • 1 <= n <= 1015
  • The answer must be computed efficiently due to the large value of n.

Thought Process

First, let's analyze what makes a number "good" according to the problem statement. For each position in the string:
  • If the index is even, we can use any of 5 even digits.
  • If the index is odd, we can use any of 4 prime digits.
The brute-force approach would be to generate all possible strings and count the ones that fit the criteria. However, with n as large as 1015, this is computationally impossible.

Instead, we notice that each position is independent: for each even index, there are 5 choices; for each odd index, there are 4 choices. The total number of good numbers is 5even\_positions * 4odd\_positions. The challenge is to compute this efficiently for very large exponents.

Solution Approach

To efficiently compute the answer, we follow these steps:
  1. Count positions:
    • Even positions: (n + 1) // 2 (since 0 is even, so for n=5, positions 0,2,4 are even)
    • Odd positions: n // 2
  2. Apply choices per position:
    • Each even position: 5 choices (even digits)
    • Each odd position: 4 choices (prime digits)
  3. Calculate the result:
    • The total number of good numbers is 5even\_positions * 4odd\_positions.
  4. Efficient exponentiation:
    • Since n is very large, use modular exponentiation (also called fast power or binary exponentiation) to compute ab mod m efficiently in O(log b) time.
  5. Return the answer modulo 10^9 + 7:
    • This prevents integer overflow and matches the problem's requirement.

Example Walkthrough

Let's walk through an example with n = 4:
  • Even indices: 0 and 2 (positions 0 and 2) ⇒ 2 positions
  • Odd indices: 1 and 3 (positions 1 and 3) ⇒ 2 positions
  • For each even index: 5 choices
  • For each odd index: 4 choices
  • Total combinations: 52 * 42 = 25 * 16 = 400
Step-by-step:
  • Pick an even digit for position 0 (5 options)
  • Pick a prime digit for position 1 (4 options)
  • Pick an even digit for position 2 (5 options)
  • Pick a prime digit for position 3 (4 options)
  • For each combination of the above, multiply the possibilities: 5 * 4 * 5 * 4 = 400
This matches our formula and shows how the answer is built from independent choices at each position.

Time and Space Complexity

  • Brute-force approach: Would be O(9^n) or worse, since you would try all digit strings of length n. This is not feasible for large n.
  • Optimized approach:
    • Counting positions: O(1)
    • Modular exponentiation: O(log n) for each call (we call it twice, for 5 and 4).
    • Total time: O(log n)
    • Space: O(1) (only a few integer variables used)

Summary

The key insight is that each position in the string can be filled independently, leading to a simple formula based on the number of even and odd indices. By using modular exponentiation, we can handle very large exponents efficiently. This approach is both elegant and optimal, reducing the problem to a few arithmetic operations and fast power calculations.