Count Good Numbers
Understanding the Problem
We need to count digit strings of length n where every digit at an even index is even (5 choices: 0, 2, 4, 6, 8) and every digit at an odd index is prime (4 choices: 2, 3, 5, 7). Each position is independent of every other position, so the total count is the product of choices at each position.
For a string of length n, there are ceil(n/2) even-indexed positions and floor(n/2) odd-indexed positions. So the answer is 5^ceil(n/2) * 4^floor(n/2) modulo 10^9 + 7.
Key Constraints:
1 <= n <= 10^15→ Any O(n) approach would need up to 10^15 iterations, which is far too slow. The exponent itself must be processed in O(log n) time, which points to binary exponentiation.- The answer is requested modulo 10^9 + 7, so intermediate products must be reduced as they are computed; the exact value of
5^ceil(n/2) * 4^floor(n/2)has on the order of 10^15 digits. - Since positions are independent, the total is a product of per-position choices, which collapses into powers.
Approach 1: Brute Force (Iterative Multiplication)
Intuition
Multiply the choices one position at a time. Position 0 is even-indexed (5 choices), position 1 is odd-indexed (4 choices), position 2 is even-indexed (5 choices), and so on. We keep a running product, taking the modulo at each step to prevent overflow.
Algorithm
- Initialize
result = 1andMOD = 10^9 + 7. - For each position
ifrom0ton - 1: - If
iis even, multiplyresultby 5. - If
iis odd, multiplyresultby 4. - Take
result % MODafter each multiplication. - Return
result.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through all n positions, doing constant work at each step. With n up to 10^15, this would take years.
- Space Complexity: O(1). The loop uses a constant number of variables regardless of input size.
At n = 10^15 this loop cannot finish in any reasonable time. The loop multiplies by 5 exactly ceil(n/2) times and by 4 exactly floor(n/2) times, so the entire computation is two powers, and powers with huge exponents can be computed in O(log n).
Approach 2: Optimal (Binary Exponentiation)
Intuition
Since each position's choice is independent, the total count is:
answer = 5^ceil(n/2) * 4^floor(n/2) mod (10^9 + 7)
where ceil(n/2) counts the even-indexed positions (indices 0, 2, 4, ...) and floor(n/2) counts the odd-indexed positions (indices 1, 3, 5, ...).
The remaining work is computing large powers efficiently. Binary exponentiation (also called fast power or exponentiation by squaring) does this in O(log n) time: if b is even, a^b = (a^(b/2))^2, and if b is odd, a^b = a * a^(b-1). Repeatedly halving the exponent reduces the number of multiplications from b down to about log(b).
The iterative version processes the exponent's binary representation directly. For example, 5^13 = 5^(1101 in binary) = 5^8 * 5^4 * 5^1. The loop computes 5^1, 5^2, 5^4, 5^8 by squaring base at each step, and multiplies into result only the powers whose binary digit is 1 (the exp % 2 == 1 check). The number of iterations equals the number of bits in the exponent, which is O(log n).
Algorithm
- Compute
evenCount = ceil(n / 2)andoddCount = floor(n / 2). - Use binary exponentiation to compute
power(5, evenCount, MOD). - Use binary exponentiation to compute
power(4, oddCount, MOD). - Return
(power(5, evenCount) * power(4, oddCount)) % MOD.
The binary exponentiation function power(base, exp, mod):
- Initialize
result = 1. - Set
base = base % mod. - While
exp > 0: - If
expis odd, multiplyresultbybaseand take mod. - Square
baseand take mod. - Halve
exp(integer division by 2). - Return
result.
Example Walkthrough
Code
- Time Complexity: O(log n). Two calls to binary exponentiation, each doing at most O(log n) iterations by halving the exponent at each step.
- Space Complexity: O(1). The binary exponentiation is an iterative loop, so it uses a constant number of variables and no recursion stack.