1922. Count Good Numbers - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You’re given a positive integer n. A good number is an n‑digit number (leading zeros allowed) where:

At even indices (0‑based), the digit is even: one of {0,2,4,6,8}.
At odd indices, the digit is a prime digit: one of {2,3,5,7}.
Return the total count of good numbers modulo 10^9 + 7.

Examples

Example 1

Input  n = 1  
Output 5  
Explanation  
Only index 0 exists, it must be even. Choices = {0,2,4,6,8} → 5 total.

Example 2

Input  n = 2  
Output 20  
Explanation  
Index 0 (even): 5 choices; index 1 (odd): 4 choices → 5×4 = 20.

Example 3

Input  n = 4  
Output 400  
Explanation  
Even positions: indices 0,2 → 2 spots → 5^2 = 25;  
Odd positions: indices 1,3 → 2 spots → 4^2 = 16;  
Total = 25×16 = 400.

Constraints

1 ≤ n ≤ 10^15
Answers must be given modulo 10^9 + 7

Hints

Compute how many even‐index slots and odd‐index slots there are for length n.
Each slot is independent: multiply the number of choices per slot, then apply the modulo.
How can you compute large exponents (like 5^(n/2)) under a modulus quickly?

Approach 1 – Straightforward Multiplication (O(n))

Idea

Multiply by 5 for each even index, by 4 for each odd index, taking the modulo at each step.

Steps

Let mod = 10^9+7, ans = 1.
For i from 0 to n−1:
- If i even: ans = ans * 5 % mod
- Else: ans = ans * 4 % mod
Return ans.

Code (Python)

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time: O(n) → impossible when n up to 10^15
Space: O(1)

Approach 2 – Fast Exponentiation (O(log n))

Idea

Count even‐index slots = ⌈n/2⌉, odd‐index slots = ⌊n/2⌋.
Result = $(5^⌈n/2⌉ \times 4^⌊n/2⌋) mod (10^9+7)$
Compute each power with binary exponentiation in O(log exponent).

Steps

Define powMod(x, e) that returns x^e mod M via fast exponentiation.
Let evenCnt = (n + 1) // 2, oddCnt = n // 2.
Return (powMod(5, evenCnt) * powMod(4, oddCnt)) % mod.

Code (Python)

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time: O(log n) per exponentiation → overall O(log n)
Space: O(1)

Step‑by‑Step Walkthrough (n = 5)

Even indices: 0,2,4 → 3 slots → 5³ = 125
Odd indices: 1,3 → 2 slots → 4² = 16
Total = 125 × 16 = 2000 → return 2000 mod 1e9+7 = 2000

Common Mistakes

Using built‑in pow(5, evenCnt) without modulo or incorrect overload.
Mixing up ⌈n/2⌉ vs ⌊n/2⌋ → off‑by‑one in slot counts.
Forgetting to modulo after multiplications → overflow.
Attempting O(n) loop for extremely large n → TLE.

Edge Cases

n = 1 → only even slot → 5
n = 2 → 5×4 = 20
Very large n (10^15) → must use fast exponentiation
Modulo arithmetic always applied

Alternative Variations

Change digit constraints (e.g. odd digits at even positions).
Vary allowed digit sets per position in a pattern → same exponentiation strategy.
Count numbers without leading zeros → adjust first‐digit multiplier.