Watch 10 video solutions for Count Good Numbers, a medium level problem involving Math, Recursion. This walkthrough by Fraz has 67,846 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).
"2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, "3245" is not good because 3 is 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 <= 1015Problem 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 | 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. |