Count Good Numbers
MedPrompt
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: 400Example 3:
Input: n = 50
Output: 564908303
Constraints:
1 <= n <= 1015
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's combinatorial logic into code. We first determine the number of even and odd positions in a string of length n. Then, we calculate the total number of permutations by raising the number of choices for each position type (5 for even, 4 for odd) to the power of their respective counts. The exponentiation is performed using a simple loop. While straightforward, this method is too slow for the given constraints.
Algorithm
- Calculate the number of even indices:
evenCount = (n + 1) / 2. - Calculate the number of odd indices:
oddCount = n / 2. - Define a function
naivePower(base, exp)that computes(base^exp) % MODusing a simple loop that iteratesexptimes. - In each iteration of the loop, multiply the running result by
baseand take the modulo. - Calculate
term1 = naivePower(5, evenCount). - Calculate
term2 = naivePower(4, oddCount). - The final result is
(term1 * term2) % MOD.
Walkthrough
The problem asks for the number of 'good' strings of length n. A good string has even digits (0, 2, 4, 6, 8) at even indices and prime digits (2, 3, 5, 7) at odd indices.
- Count Positions: For a string of length
n, there are(n + 1) / 2even indices andn / 2odd indices. - Count Choices: There are 5 choices for each even position and 4 choices for each odd position.
- Total Permutations: The total number of good strings is
(5 ^ ((n + 1) / 2)) * (4 ^ (n / 2)), all calculated modulo10^9 + 7.
The naive approach implements a power function that uses a simple loop to perform multiplication.
private long naivePower(long base, long exp) { long res = 1; long MOD = 1_000_000_007; base %= MOD; for (long i = 0; i < exp; i++) { res = (res * base) % MOD; } return res;} public int countGoodNumbers(long n) { long MOD = 1_000_000_007; long evenCount = (n + 1) / 2; long oddCount = n / 2; long evenPermutations = naivePower(5, evenCount); long oddPermutations = naivePower(4, oddCount); return (int)((evenPermutations * oddPermutations) % MOD);}This approach is too slow because the exponent exp can be as large as 10^15. A loop running that many times will result in a 'Time Limit Exceeded' error.
Complexity
Time
O(n). The `naivePower` function has a time complexity of O(exponent). Since the exponents are proportional to `n`, the overall complexity is O(n).
Space
O(1). The algorithm uses a constant amount of extra space.
Trade-offs
Pros
Very simple to understand and implement.
Cons
Extremely inefficient for large values of
n.Will cause a 'Time Limit Exceeded' error on most platforms for the given constraints.
Solutions
Solution
class Solution {private int mod = 1000000007;public int countGoodNumbers(long n) { return (int)(myPow(5, (n + 1) >> 1) * myPow(4, n >> 1) % mod); }private long myPow(long x, long n) { long res = 1; while (n != 0) { if ((n & 1) == 1) { res = res * x % mod; } x = x * x % mod; n >>= 1; } return res; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.