Count Good Numbers - Solution & Explanation
Problem Statement
A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).
- For example,
"2582"is good because the digits (2and8) at even positions are even and the digits (5and2) at odd positions are prime. However,"3245"is not good because3is at an even index but is not even.
Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 109 + 7.
A digit string is a string consisting of digits 0 through 9 that may contain leading zeros.
Example 1:
Input: n = 1 Output: 5 Explanation: The good numbers of length 1 are "0", "2", "4", "6", "8".
Example 2:
Input: n = 4 Output: 400
Example 3:
Input: n = 50 Output: 564908303
Constraints:
1 <= n <= 1015
Approach Overview
Problem Overview: You need to count how many digit strings of length n are considered good. A digit at an even index (0‑based) must be an even digit (0,2,4,6,8) and a digit at an odd index must be a prime digit (2,3,5,7). Because n can be extremely large, directly constructing or iterating through strings is impossible. The task reduces to counting valid choices using math and computing the result modulo 1e9 + 7.
Approach 1: Iterative Approach with Modulo Calculations (O(n) time, O(1) space)
This approach computes the number of choices position by position. Every even index contributes 5 choices (even digits), and every odd index contributes 4 choices (prime digits). Iterate from 0 to n-1, multiply the running result by 5 or 4 depending on the index parity, and apply modulo 1e9+7 at each step to avoid overflow. The logic is straightforward and mirrors the problem definition directly. However, when n is very large (up to 10^15 in constraints), an O(n) loop becomes impractical.
Approach 2: Combine Properties of Even and Prime Numbers (Fast Power) (O(log n) time, O(log n) space)
The key observation: positions are independent. Count how many even indices and odd indices exist instead of processing each one. Even indices = ceil(n / 2), odd indices = floor(n / 2). Each even index has 5 choices and each odd index has 4 choices. The total number of good numbers becomes 5^(ceil(n/2)) * 4^(floor(n/2)). Compute these powers using fast modular exponentiation (binary exponentiation), which repeatedly squares the base and halves the exponent. This reduces the runtime from O(n) to O(log n). Implementations often use recursion or iterative binary exponentiation, making this approach a strong example of combining math with recursion and modular arithmetic.
Recommended for interviews: Interviewers expect the mathematical reduction and fast exponentiation approach. Starting with the iterative counting idea demonstrates you understand the constraints and combinatorics. The optimized solution shows you recognize exponential growth patterns and apply modular exponentiation to handle huge inputs efficiently.
Approach 1: Combine Properties of Even and Prime Numbers
The task is to construct a good digit string of length n. We need to ensure that digits at even indices are even and those at odd indices are prime numbers.
- The even-indexed positions (0, 2, 4, ...) should contain one of the five even digits (0, 2, 4, 6, 8).
- The odd-indexed positions (1, 3, 5, ...) should contain one of the four prime numbers (2, 3, 5, 7).
We calculate the number of ways to fill the even and odd positions independently.
This solution employs a modular exponentiation function to handle large powers efficiently. Since the result must be returned modulo 10^9 + 7, we use the function power() to compute powers of 5 and 4, which represent the choices for even and odd-indexed positions.
Complexity
The time complexity is O(log n) due to the logarithmic time complexity of the power function. The space complexity is O(1) since we are using a constant amount of extra space.
Approach 2: Iterative Approach with Modulo Calculations
An iterative approach can also be used to solve this problem by calculating the number of valid numbers at each step sequentially rather than relying on exponentiation.
This implementation directly iterates through each potential position n, multiplying by 5 or 4 as appropriate and taking the modulus at each step, resulting in an efficient solution without external power functions.
Complexity
Time complexity is O(n) due to direct iteration through each step. Space complexity remains O(1) as no additional allocations are performed.
Approach 3: Fast Exponentiation
For a "good number" of length n, the even-indexed positions have \lceil \frac{n}{2} \rceil = \lfloor \frac{n + 1}{2} \rfloor digits, and these positions can be filled with 5 different digits (0, 2, 4, 6, 8). The odd-indexed positions have \lfloor \frac{n}{2} \rfloor digits, and these positions can be filled with 4 different digits (2, 3, 5, 7). Therefore, the total number of "good numbers" of length n is:
$
ans = 5^{\lceil \frac{n}{2} \rceil} times 4^{\lfloor \frac{n}{2} \rfloor}
We can use fast exponentiation to compute 5^{\lceil \frac{n}{2} \rceil} and 4^{\lfloor \frac{n}{2} \rfloor}. The time complexity is O(log n), and the space complexity is O(1)$.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Combine Properties of Even and Prime Numbers | The time complexity is |
| Iterative Approach with Modulo Calculations | Time complexity is |
| Fast Exponentiation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Multiplication with Modulo | O(n) | O(1) | When n is small and you want the most direct implementation matching the problem definition. |
| Mathematical Counting + Fast Modular Exponentiation | O(log n) | O(log n) | Preferred for large n. Uses exponentiation by squaring to compute 5^(ceil(n/2)) and 4^(floor(n/2)) efficiently. |
Video Solution
Leetcode Solution : Count Good Numbers • Fraz • 70,819 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Good Numbers easy or hard?
How to solve Count Good Numbers in O(log n)?
What is the best approach for Count Good Numbers?
Is Count Good Numbers asked at Google/Amazon/Meta?
What data structure is used in Count Good Numbers?
What is the time complexity of Count Good Numbers?
Count Good Numbers Python or Java solution approach?
Ready to solve this problem?
Practice Count Good Numbers with our built-in code editor and test cases.
Practice on FleetCode