DSA problem
Count Good Numbers
A digit string of length n is called good when:
- The digits in even-indexed positions (0, 2, 4, ...) are all even — i.e. one of
0, 2, 4, 6, 8. - The digits in odd-indexed positions (1, 3, 5, ...) are all prime — i.e. one of
2, 3, 5, 7.
Given an integer n, return the count of digit strings of length n that are good. Because the answer can be astronomically large, return it modulo 10^9 + 7.
The structure is purely combinatorial. There are ceil(n / 2) even-indexed slots and floor(n / 2) odd-indexed slots. Each even-indexed slot has 5 valid digits (the evens) and each odd-indexed slot has 4 valid digits (the primes 2, 3, 5, 7). Since the choices at different positions are independent, the total count is 5^ceil(n/2) * 4^floor(n/2) modulo 10^9 + 7.
Because n can be as large as 10^15, we cannot iterate n times. Use modular fast exponentiation (binary exponentiation) to compute each power in O(log n) time. Be careful with overflow: in languages without arbitrary-precision integers (Java, C++, JavaScript with care), do intermediate multiplications in 64-bit (long / long long / BigInt) before applying the modulus.
Examples
n = 15n = 4400n = 50564908303Constraints
- 1 <= n <= 10^15
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.