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