Count Good Numbers — Solution in Python, Java & C++
Count Good Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on math and recursion.
Count Good Numbers is a medium coding problem on math and recursion, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Math, Recursion
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A digit string (leading zeros allowed) is good when every digit at an even index (0-indexed) is even — 0, 2, 4, 6 or 8 — and every digit at an odd index is a prime — 2, 3, 5 or 7.
For example, "2582" is good, while "3245" is not (index 0 holds 3, which is odd).
Return how many good digit strings of length n exist, modulo 10^9 + 7. (Here n fits in a 32-bit integer; the original problem allows lengths up to 10^15.)
Example 1
Input: n = 1
Output: 5
Explanation: "0", "2", "4", "6" and "8".
Example 2
Input: n = 4
Output: 400
Explanation: Two even positions with 5 choices and two odd positions with 4 choices: 5·4·5·4.
Example 3
Input: n = 50
Output: 564908303
Constraints
1 <= n <= 2 * 10^9
Hints for Count Good Numbers
Hint 1
Positions are independent: each even index has 5 choices, each odd index has 4.
Hint 2
There are
ceil(n / 2)even indices andfloor(n / 2)odd ones, so the count is5^ceil(n/2) · 4^floor(n/2).Hint 3
The exponents reach 10^9 — use fast exponentiation by squaring, reducing modulo 10^9 + 7 after every multiplication.
How to solve Count Good Numbers
The choice at each position is independent of every other, so the count is a product of powers, computed with binary exponentiation.
Approach
- Let
even = (n + 1) / 2andodd = n / 2(integer division). - Compute
5^even mod Mand4^odd mod Mby repeated squaring: square the base each round and multiply it into the result when the current exponent bit is 1. - Return their product modulo
M = 10^9 + 7.
Why it works
A good string is exactly a choice of an even digit for each of the ceil(n/2) even indices and a prime digit for each of the floor(n/2) odd indices, and every combination gives a distinct string — the multiplication principle gives 5^even · 4^odd. Repeated squaring uses b^e = (b²)^(e/2) (times b when e is odd), so it needs only O(log n) multiplications, and reducing after each keeps every value below M.
Complexity
- Time —
O(log n) - Space —
O(1)
Pitfalls
- Two residues below 10^9 + 7 multiply to ~10^18: use 64-bit integers, and in JavaScript split the multiplication (or the product loses precision past 2^53).
- Index 0 is even: an odd
nhas one more even position than odd ones. - A loop that multiplies
ntimes is far too slow for n = 2·10^9.
Reference solution
Python
def countGoodNumbers(n: int) -> int:
MOD = 10 ** 9 + 7
return pow(5, (n + 1) // 2, MOD) * pow(4, n // 2, MOD) % MODJava
public static int countGoodNumbers(int n) {
long even = ((long) n + 1) / 2, odd = n / 2;
return (int) (goodPow(5, even) * goodPow(4, odd) % 1000000007L);
}
private static long goodPow(long b, long e) {
final long MOD = 1000000007L;
long r = 1;
b %= MOD;
while (e > 0) {
if ((e & 1) == 1) r = r * b % MOD;
b = b * b % MOD;
e >>= 1;
}
return r;
}C++
long long goodPow(long long b, long long e) {
const long long MOD = 1000000007LL;
long long r = 1;
b %= MOD;
while (e > 0) {
if (e & 1) r = r * b % MOD;
b = b * b % MOD;
e >>= 1;
}
return r;
}
int countGoodNumbers(int n) {
long long even = ((long long) n + 1) / 2, odd = n / 2;
return (int) (goodPow(5, even) * goodPow(4, odd) % 1000000007LL);
}JavaScript
var countGoodNumbers = function(n) {
var MOD = 1000000007;
var mulMod = function(a, b) {
var hi = Math.floor(b / 65536), lo = b % 65536;
return ((a * hi) % MOD * 65536 + a * lo) % MOD;
};
var powMod = function(b, e) {
var r = 1;
b %= MOD;
while (e > 0) {
if (e % 2 === 1) r = mulMod(r, b);
b = mulMod(b, b);
e = Math.floor(e / 2);
}
return r;
};
return mulMod(powMod(5, Math.floor((n + 1) / 2)), powMod(4, Math.floor(n / 2)));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Recursion