PPractick

The problem

A lock manufacturer wants to count how many n-digit codes (leading zeros allowed) satisfy its "good code" rule: digits at even indices (0, 2, 4, …) must be even (0, 2, 4, 6, 8, so 5 choices), and digits at odd indices must be prime (2, 3, 5, 7, so 4 choices). n can be as large as 10¹⁵, so the answer is reported modulo 10⁹ + 7. The count is simply 5^(even positions) · 4^(odd positions); the real task is computing huge powers quickly with recursive fast exponentiation.

Example: n = 1 → 5 (the codes 0, 2, 4, 6, 8); n = 4 → 5 · 4 · 5 · 4 = 400.

Function signature

int countGoodNumbers(long long n);  // 1 <= n <= 10^15; result modulo 1e9 + 7

Test cases

Input n	Output	Explanation
1	5	One even position
2	20	5 · 4
3	100	5 · 4 · 5
4	400	5² · 4²
50	564908303	5²⁵ · 4²⁵ mod 1e9 + 7

(Confirm: indices are 0-based; leading zeros are allowed; the answer is taken modulo 1,000,000,007.)

How interviewers phrase it

• "A digit string is good if digits at even indices are even and digits at odd indices are prime. Return the number of good digit strings of length n, modulo 10⁹ + 7" (LeetCode 1922).

Clarifying questions to ask

1. Are indices 0-based? (Yes, so index 0 must be even.)
2. Are leading zeros allowed? (Yes, it's a digit string.)
3. How large can n be? (Up to 10¹⁵, which rules out any O(n) loop.)

Follow-ups to expect

1. "Why is it a product?"
2. "How many even and odd positions are there?"
3. "Why fast exponentiation?"
4. "Where can overflow happen?"
5. "Complexity?"

Related questions

• Word Break Medium
• Fibonacci Number Easy
• Pow(x, n) Easy
• Largest BST in Binary Tree Hard
• Merge Sorting Medium
• Quick Sorting Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in