Count Good Numbers

Problem in Plain English

Count length-n decimal strings with even digits at even indices and prime digits at odd indices. Leading zero is allowed; return the count modulo 1,000,000,007.

Problem Statement

A good digit string has one of 0,2,4,6,8 at each even index and one of 2,3,5,7 at each odd index, using zero-based indices. Given n, return the number of good strings of length n, modulo 10^9 + 7. Leading zeros are allowed, so the first position has five choices just like every other even position.

For example, 2582 is good and 3245 is not. The official problem permits n up to 10^15, making a loop through every position impractical.

Constraints

1 <= n <= 10^15.
Return a residue modulo 10^9 + 7; strings may begin with zero.

Examples

Example 1

Input: n = 1
Output: 5

The five good strings are 0, 2, 4, 6 and 8. There are zero complete pairs and one extra even position.

Example 2

Input: n = 4
Output: 400

Two complete pairs give 20 × 20 = 400, equivalently 5 × 4 × 5 × 4.

Example 3

Input: n = 50
Output: 564908303

There are 25 complete pairs. Reducing 20^25 modulo 1,000,000,007 gives 564908303.

Example 4

Input: n = 3
Output: 100

One complete pair gives twenty choices and the final even position gives five more: 20 × 5 = 100.

Intuition

Independent positions multiply their choices: there are five choices at each of the ceil(n/2) even indices and four at each of the floor(n/2) odd indices. Thus the answer is 5^ceil(n/2) × 4^floor(n/2) modulo the required modulus. In Example 1, the single even position allows 0, 2, 4, 6 or 8. Pairing one even and one odd position gives twenty possibilities; count complete pairs with fast exponentiation and multiply by five if one even position remains. Residues stay small after reduction, but multiplying two residues can still approach 10^18, so JavaScript needs exact integer multiplication.

Approaches

Modular Power

Optimal

Solution Details

Reveal Modular Power: intuition, complexity, and code

Intuition

Compute twenty raised to the number of complete position pairs by repeated squaring, then account for a possible final even position. A linear product uses n multiplications; halving the exponent at each iteration needs only O(log n). Whenever the exponent is odd, multiply the accumulator by the current base, then square the base and halve the exponent. Reducing after every multiplication preserves the final residue because congruent integers have congruent products. Java uses long, Python uses integers, and JavaScript uses BigInt for every modular product. To see the loop execute, use Example 2 with n = 4: initialize (exponent, base, result) = (2,20,1). The even iteration skips accumulation, squares 20 to 400, and halves 2 to 1, giving (1,400,1). The odd iteration accumulates 400, squares the base to 160000, and halves 1 to 0, giving (0,160000,400). The length is even, so the final answer is 400.

Step-by-Step Logic

For Example 1, initialize result = 1, base = 20, and exponent = floor(1/2) = 0.
The exponentiation loop has no iterations because there are no complete pairs.
Length 1 is odd, so multiply result by 5 modulo 1,000,000,007.
Return 5; in JavaScript the final residue alone converts back to Number.

Why It Works

The multiplication rule counts each legal string once because its independent digit choices determine it uniquely. Each pair contributes exactly 5 × 4 = 20 choices, and an odd length has a final even index with five choices. For exponentiation, preserve result × base^exponent congruent to the original 20^floor(n/2) modulo the modulus. With an odd exponent, transferring one base factor to result leaves an even exponent. Squaring base and replacing the remaining exponent by its half preserves the product. At exponent zero, result is the required pair count. Multiplying by five for odd n finishes the count. Modulo reduction can occur at every step by the product law of congruence. No primality assumption on the modulus is needed for this algorithm.

Dry Run

Modular Power: variable states at each step
Stage	base	result
Initialize for n = 1	20	1
Loop condition false	20	1
Odd-length extra position	20	5
Return residue	20	5

Complexity Analysis

Time Complexity

O(log n)

Space Complexity

O(1)

Each loop halves floor(n/2), requiring at most 49 iterations under the stated bound, with a constant number of bounded integer variables and no recursion. Java products are at most (1,000,000,006)^2, below Long.MAX_VALUE. JavaScript n is a safe integer under 10^15, but residue products can exceed Number.MAX_SAFE_INTEGER; BigInt preserves them exactly. The returned residue fits Number safely.

Code

Solution.java

1class Solution {2    public int countGoodNumbers(long n) {3        long mod = 1_000_000_007L;4        long result = 1, base = 20, exponent = n / 2;5        while (exponent > 0) {6            if (exponent % 2 == 1) result = result * base % mod;7            base = base * base % mod;8            exponent /= 2;9        }10        if (n % 2 == 1) result = result * 5 % mod;11        return (int) result;12    }13}

Hints

Hint 1

How many choices does each position have, including the first?

Hint 2

Pair successive even and odd indices: each pair contributes twenty independent choices.

Hint 3

Compute 20^floor(n/2) modulo the modulus by squaring and halving; multiply by five when n is odd.

Edge Cases

Length one has five choices including zero; excluding leading zero would give the wrong answer.
For an odd length such as three, the extra final position is even, contributing five rather than four.
At n = 10^15, iteration by position is infeasible, but exponentiation still takes fewer than fifty iterations.

Common Mistakes and Interview Tips

Using Number for base * base and applying % afterward cannot restore digits already lost to rounding.
Using Java int for a residue product overflows before reduction; both operands must be long.
Using JavaScript exponent >> 1 truncates the exponent to 32 bits; BigInt division handles the full input bound.
Treating the strings as positive integers mistakenly bans a leading zero.

Key Takeaway

Independent choices produce powers. Binary exponentiation evaluates huge exponents with few operations, while modular reduction controls operand sizes only if each multiplication is exact in the chosen runtime.