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.
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.
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.
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.
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.
Time complexity is O(n) due to direct iteration through each step. Space complexity remains O(1) as no additional allocations are performed.
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)$.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Combine Properties of Even and Prime Numbers | The time complexity is |
| Iterative Approach with Modulo Calculations | Time complexity is |
| Fast Exponentiation | — |
| 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. |
Leetcode Solution : Count Good Numbers • Fraz • 67,846 views views
Watch 9 more video solutions →Practice Count Good Numbers with our built-in code editor and test cases.
Practice on FleetCode