Count Good Numbers

Count Good Numbers

What is this problem about?

The Count Good Numbers interview question defines a "good" number as one where digits at even indices (0, 2, 4...) are even (0, 2, 4, 6, 8) and digits at odd indices (1, 3, 5...) are prime (2, 3, 5, 7). Given a length n, you need to find the total number of good numbers of that length. Return the answer modulo 10^9 + 7.

Why is this asked in interviews?

Amazon and Google ask the Recursion / Math interview pattern for this problem to test your ability to handle large exponents and modular arithmetic. Since n can be up to 10^15, you must use Binary Exponentiation. It evaluates whether you can derive a simple combinatorial formula and implement it efficiently.

Algorithmic pattern used

This is a Combinatorics and Binary Exponentiation problem.

1. Number of even positions = ceil(n / 2).
2. Number of odd positions = floor(n / 2).
3. Available even digits: 5 (0, 2, 4, 6, 8).
4. Available prime digits: 4 (2, 3, 5, 7).
5. Total good numbers = (5^even_pos * 4^odd_pos) % (10^9 + 7).
6. Use Modular Exponentiation (power function) to calculate these large powers in O(log N) time.

Example explanation

n = 1

• Even positions: 1. 5^1 = 5. Result: 5.

n = 4

• Even positions (0, 2): 2. 5^2 = 25.
• Odd positions (1, 3): 2. 4^2 = 16.
• Total = 25 * 16 = 400. Result: 400.

Common mistakes candidates make

• Integer Overflow: Using standard pow() or a loop, which will overflow or time out. You must use a custom modular exponentiation function.
• Wrong Digit Count: Including '1' or '9' as primes, or forgetting that '0' is an even digit.
• Positioning: Mixing up the rules for even and odd indices.

Interview preparation tip

Modular exponentiation is a "top 10" algorithm for competitive programming and technical interviews. Practice implementing pow(base, exp, mod) recursively or iteratively.