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.
This is the optimal approach for this problem. It leverages a mathematical technique called Binary Exponentiation (or Exponentiation by Squaring) to calculate powers in logarithmic time. The core idea is to reduce the exponent by half at each step, drastically cutting down the number of required multiplications. This efficiency makes it possible to handle the large exponents derived from n up to 10^15.
Algorithm
- Calculate the number of even indices:
evenCount = (n + 1) / 2. - Calculate the number of odd indices:
oddCount = n / 2. - Implement an efficient
power(base, exp)function using the binary exponentiation algorithm. - Inside the
powerfunction, iterate whileexp > 0. In each step, ifexpis odd, multiply the result by the currentbase. Then, square thebaseand halve theexp. - Calculate
term1 = power(5, evenCount). - Calculate
term2 = power(4, oddCount). - The final result is
(term1 * term2) % MOD.
Walkthrough
The combinatorial formula remains the same: Total = (5 ^ evenCount) * (4 ^ oddCount) % MOD. The challenge is computing a^b % MOD where b is large.
Binary Exponentiation solves this efficiently. It is based on the following properties:
- If the exponent
bis even,a^b = (a^2)^(b/2). - If the exponent
bis odd,a^b = a * a^(b-1) = a * (a^2)^((b-1)/2).
By repeatedly applying these rules, we can compute the power in O(log b) time. We can implement this both recursively and iteratively. The iterative approach is generally preferred as it avoids potential stack overflow and uses O(1) space.
Here is the implementation using an iterative fast power function:
class Solution { long MOD = 1_000_000_007; private long power(long base, long exp) { long res = 1; base %= MOD; while (exp > 0) { if (exp % 2 == 1) { res = (res * base) % MOD; } base = (base * base) % MOD; exp /= 2; // or exp >>= 1; } return res; } public int countGoodNumbers(long n) { long evenCount = (n + 1) / 2; long oddCount = n / 2; long evenPermutations = power(5, evenCount); long oddPermutations = power(4, oddCount); return (int)((evenPermutations * oddPermutations) % MOD); }}This algorithm is highly efficient and is the standard way to solve problems involving modular exponentiation with large powers.
Complexity
Time
O(log n). The `power` function runs in time proportional to the number of bits in the exponent, which is `log(exponent)`. Since the exponents are proportional to `n`, the overall complexity is O(log n).
Space
O(1). The iterative implementation of binary exponentiation uses a constant amount of extra space.
Trade-offs
Pros
Extremely efficient, with logarithmic time complexity.
The standard solution for modular exponentiation problems.
Easily handles the large constraints on
n.
Cons
Slightly more complex to understand initially compared to the naive loop.
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; }}int MOD = 1000000007 ; class Solution { public: int countGoodNumbers ( long long n ) { return ( int ) ( myPow ( 5 , ( n + 1 ) >> 1 ) * myPow ( 4 , n >> 1 ) % MOD ); } private: long long myPow ( long long x , long long n ) { long long res = 1 ; while ( n ) { if (( n & 1 ) == 1 ) { res = res * x % MOD ; } x = x * x % MOD ; n >>= 1 ; } return res ; } };class Solution: def countGoodNumbers(self, n: int) -> int: mod = 10 ** 9 + 7 def myPow(x, n): res = 1 while n: if (n & 1) == 1: res = res * x % mod x = x * x % mod n >>= 1 return res return myPow(5, (n + 1) >> 1) * myPow(4, n >> 1) % modVideo 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.