Count Good Numbers: Modular Exponentiation

A digit string is "good" if the digit at every even index (0-indexed) is even (0, 2, 4, 6, 8) and the digit at every odd index is prime (2, 3, 5, 7). Given an integer n, return the total number of good digit strings of length n. Since the answer can be huge, return it modulo 10^9 + 7.

This is LeetCode 1922: Count Good Numbers. A few examples:

• n = 1 returns 5 (only even-index positions: five choices 0, 2, 4, 6, 8)
• n = 4 returns 400 (5 * 4 * 5 * 4)
• n = 50 returns 564908303

The constraint 1 <= n <= 10^15 rules out any approach that loops through all n positions individually. You need a way to compute the answer in O(log n) time.

The approach

Think about what happens at each position in the digit string. You have n positions, indexed from 0 to n - 1.

• Even-indexed positions (0, 2, 4, ...): the digit must be even. There are 5 even digits (0, 2, 4, 6, 8), so each position has 5 valid choices.
• Odd-indexed positions (1, 3, 5, ...): the digit must be prime. There are 4 single-digit primes (2, 3, 5, 7), so each position has 4 valid choices.

Since the choice at each position is independent, the total count is the product of choices across all positions:

answer = 5^(number of even indices) * 4^(number of odd indices)

How many even indices are there? For a string of length n, the even indices are 0, 2, 4, ..., which gives ceil(n / 2) positions. The odd indices are 1, 3, 5, ..., which gives floor(n / 2) positions.

So the formula is:

answer = 5^ceil(n/2) * 4^floor(n/2) mod (10^9 + 7)

Why you need fast exponentiation

The formula looks simple, but n can be as large as 10^15. You cannot compute 5^(500000000000000) by multiplying 5 by itself half a quadrillion times. That would take far too long.

Binary exponentiation (also called exponentiation by squaring) solves this. Instead of n multiplications, you need only O(log n) multiplications. The idea is:

• If the exponent is even: a^e = (a^(e/2))^2
• If the exponent is odd: a^e = (a^(e/2))^2 * a
• Base case: a^0 = 1

At each step you halve the exponent and square the result. After about 50 steps (log2 of 10^15), you are done.

In Python, the built-in pow(base, exp, mod) already implements this as modular exponentiation. It computes base^exp mod mod efficiently using binary exponentiation internally.

Python solution

def countGoodNumbers(n):
    MOD = 10**9 + 7
    even_count = (n + 1) // 2
    odd_count = n // 2
    return pow(5, even_count, MOD) * pow(4, odd_count, MOD) % MOD

Walkthrough

Let's trace through countGoodNumbers(50) step by step to see how binary exponentiation keeps the computation fast and the numbers small.

The entire computation finishes in about 50 squarings and a handful of multiplications. Every intermediate value stays below 10^9 + 7 thanks to the modular reduction at each step.

Complexity analysis

The O(log n) approach handles n = 10^15 in roughly 50 steps. The O(n) approach would need a quadrillion steps, which is not feasible.

Edge cases to watch for

Before submitting, make sure your solution handles these:

• n = 1: Only one position at index 0 (even). Answer is 5. There are no odd-indexed positions, so 4^0 = 1 and 5 * 1 = 5.
• n = 2: Two positions. Index 0 is even (5 choices), index 1 is odd (4 choices). Answer is 5 * 4 = 20.
• Large n (10^15): The answer fits in a standard integer after modular reduction. Python's pow(base, exp, mod) handles this natively. In other languages, you need to implement modular exponentiation yourself.
• Overflow in other languages: When multiplying two numbers that are each up to 10^9 + 6, the intermediate product can exceed 2^62. In C++ or Java, use 64-bit integers (long long / long) and reduce modulo at each multiplication step.

The building blocks

This problem is built on two reusable patterns:

Modular exponentiation (binary exponentiation). When you need to compute a^n mod m for very large n, binary exponentiation reduces the work from O(n) to O(log n) multiplications. This is the same technique used in cryptography (RSA relies on modular exponentiation), competitive programming, and any problem where you need to raise a number to a massive power under a modulus. Python's three-argument pow(a, n, m) does this for you, but knowing how it works under the hood is essential for interviews and for languages without a built-in.

Counting with the multiplication principle. When a composite object (like a digit string) is built from independent choices at each position, the total count is the product of choices. This principle is the foundation of combinatorics and shows up constantly in counting problems: permutations, combinations, arrangements with constraints. Here, recognizing that even and odd positions are independent turns a potentially complex counting problem into two simple exponentiations.

From understanding to recall

You have seen how the problem reduces to a formula (5^even * 4^odd mod MOD) and how binary exponentiation makes that formula computable even for n = 10^15. The solution is just three lines of Python.

But under interview pressure, you need the full chain to surface instantly: independent positions, multiplication principle, modular exponentiation. That means not just understanding the derivation once, but being able to reproduce it from scratch. The formula itself is easy to forget if you only see it once, because there is nothing to "debug" or iterate on. It either clicks or it does not.

Spaced repetition locks this in. You solve the problem from scratch today, again in two days, then four days, then a week. Each time, you re-derive the formula, recall that ceil(n/2) gives the even-position count, and write the three-argument pow call from memory. After a few rounds, the pattern is yours.

Related posts

• Pow(x, n) - The foundation of binary exponentiation, where halving the exponent and squaring the result turns O(n) into O(log n)
• Count Primes - Another number theory problem where recognizing mathematical structure (the Sieve of Eratosthenes) replaces brute-force checking
• Factorial Trailing Zeroes - A math problem that uses prime factor counting and repeated division, the same flavor of "reduce the problem to a formula" thinking