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 <= 1015The key observation in #1922 Count Good Numbers is that digits at even and odd indices have different constraints. Even indices can contain any even digit (0,2,4,6,8), giving 5 choices. Odd indices must contain a prime digit (2,3,5,7), giving 4 choices. Instead of constructing all possible numbers, we count combinations mathematically.
If the length of the number is n, the total count becomes 5^(ceil(n/2)) * 4^(floor(n/2)). Since n can be very large, directly computing powers would be inefficient. The optimal strategy is to use fast modular exponentiation (often implemented with recursion or binary exponentiation) under modulo 1e9 + 7. This approach efficiently computes large powers while avoiding overflow.
By reducing the problem to mathematical counting and using fast exponentiation, we achieve a highly efficient solution suitable for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Fast Modular Exponentiation (Binary Power) | O(log n) | O(log n) recursion or O(1) iterative |
Fraz
Use these hints if you're stuck. Try solving on your own first.
Is there a formula we can use to find the count of all the good numbers?
Exponentiation can be done very fast if we looked at the binary bits of n.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of mathematical counting and modular exponentiation problems are common in FAANG-style interviews. This problem tests number theory concepts, optimization using fast power, and handling very large inputs efficiently.
This problem primarily relies on mathematical reasoning rather than data structures. The key implementation detail is an efficient power function, often written using recursion or an iterative binary exponentiation technique.
The optimal approach uses mathematical counting combined with fast modular exponentiation. Even positions contribute 5 choices and odd positions contribute 4 choices, so the result becomes 5^(ceil(n/2)) * 4^(floor(n/2)) mod 1e9+7. Fast power reduces the computation time to O(log n).
The value of n can be extremely large, making direct power computation impractical. Fast exponentiation (binary exponentiation) calculates powers in logarithmic time by repeatedly squaring the base. This keeps the solution efficient and prevents overflow when used with modulo arithmetic.