#1922

Medium

LeetCode Problem Workspace

Count Good Numbers

Count Good Numbers uses a mathematical pattern with recursion to efficiently count digit strings of length n under strict rules.

math recursion

Problem Statement

A digit string is considered good if every digit at an even index is even, and every digit at an odd index is prime (2, 3, 5, or 7). Digits are zero-indexed, and strings may start with zero.

Given an integer n, determine how many good digit strings of length n exist. Return the result modulo 10^9 + 7 because the count can be very large. This requires handling large powers efficiently using math and recursion techniques.

Examples

Example 1

Input: n = 1

Output: 5

The good numbers of length 1 are "0", "2", "4", "6", "8".

Example 2

Input: n = 4

Output: 400

Example details omitted.

Example 3

Input: n = 50

Output: 564908303

Example details omitted.

Constraints

1 <= n <= 1015

Solution Approach

Identify the pattern

Observe that positions at even indices can have 5 choices (0,2,4,6,8) and odd indices have 4 prime choices (2,3,5,7). The total count is thus 5^(number of even positions) * 4^(number of odd positions).

Apply modular exponentiation

Use fast exponentiation recursively to compute 5^(n//2 + n%2) and 4^(n//2) modulo 10^9+7. This prevents integer overflow and maintains efficiency for large n.

Combine results

Multiply the computed powers under modulo to get the total number of good numbers. This approach directly leverages the problem's mathematical pattern and recursion structure.

Complexity Analysis

Metric	Value
Time	O(\log n)
Space	O(1)

Time complexity is O(log n) due to fast exponentiation recursion, and space complexity is O(1) since no additional arrays or recursion stacks grow with n.

What Interviewers Usually Probe

Check if candidate recognizes the even/prime index pattern immediately.
Watch for attempts to generate all strings, which fails for large n.
Listen for use of fast power recursion or modular arithmetic, signaling optimal approach.

Common Pitfalls or Variants

Common pitfalls

Trying to enumerate all strings leads to memory overflow or timeout.
Miscounting even vs odd positions when n is odd.
Neglecting modulo operation and causing integer overflow.

Follow-up variants

Change the set of prime digits or even digits to test adaptability of the power calculation.
Ask for sum of digits of all good numbers instead of count, requiring extension of the pattern.
Restrict digit strings to exclude leading zeros, modifying the first position choices.

FAQ

What makes a number good in the Count Good Numbers problem?

A good number has even digits at even indices and prime digits (2,3,5,7) at odd indices.

How can I handle very large n without timing out?

Use modular exponentiation with recursion or iterative fast power methods to compute counts efficiently.

Why is modulo 10^9+7 needed?

The total count grows exponentially with n, so modulo prevents integer overflow and fits standard constraints.

Can I generate all good digit strings to count them?

No, generating strings is infeasible for large n; recognizing the pattern and using exponentiation is required.

What pattern does this problem illustrate?

It demonstrates a Math plus Recursion pattern, leveraging index-specific choices and modular exponentiation.

terminal

Solution

Solution 1: Fast Exponentiation

For a "good number" of length $n$, the even-indexed positions have $\lceil \frac{n}{2} \rceil = \lfloor \frac{n + 1}{2} \rfloor$ digits, and these positions can be filled with $5$ different digits ($0, 2, 4, 6, 8$). The odd-indexed positions have $\lfloor \frac{n}{2} \rfloor$ digits, and these positions can be filled with $4$ different digits ($2, 3, 5, 7$). Therefore, the total number of "good numbers" of length $n$ is:

1

2

3

4

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        mod = 10**9 + 7
        return pow(5, (n + 1) >> 1, mod) * pow(4, n >> 1, mod) % mod

Continue Practicing

#1969 minimum non zero product of the array elements #1823 find the winner of the circular game #1808 maximize number of nice divisors