Count Good Numbers
Medium Modular exponentiation
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A digit string is "good" if digits at even indexes are even (0,2,4,6,8) and digits at odd indexes are prime (2,3,5,7). Count good strings of length n, modulo 1e9+7. n can be up to 10^15.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: even positions can hold 5 digits, odd positions 4 digits. How many strings of length n (up to 10^15)?
Why this works: choices multiply: 5^(even count) × 4^(odd count). Fast power with modulo handles the huge exponent.
Example: n = 4
positions 0,1,2,3 → 2 even, 2 odd5² × 4² = 25 × 16 = 400
✦Hints open one at a time
↗Approach
Count the positions, then compute both powers with modular binary exponentiation and multiply them under the modulus.
</>Solution (Java)
class Solution {
private static final long MOD = 1_000_000_007L;
public int countGoodNumbers(long n) {
long even = (n + 1) / 2, odd = n / 2;
return (int) (pow(5, even) * pow(4, odd) % MOD);
}
private long pow(long base, long exp) {
long result = 1;
base %= MOD;
while (exp > 0) {
if ((exp & 1) == 1) result = result * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return result;
}
}!Common mistake
Taking the modulus only at the end. Every multiplication must be reduced, or a long overflows.
- Time: O(log n).
- Space: O(1).
