Count Good Numbers

Problem Description

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7). Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 10^9 + 7.

Key Insights

• Even indexed positions can only contain the digits 0, 2, 4, 6, or 8 (5 choices).
• Odd indexed positions can only contain the digits 2, 3, 5, or 7 (4 choices).
• The length of the string determines the number of even and odd positions. For example:
  • If n is even: there are n/2 even indices and n/2 odd indices.
  • If n is odd: there are (n/2) + 1 even indices and n/2 odd indices.
• The total number of good digit strings can be computed as the product of the choices for even and odd indexed positions.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

To solve the problem, we can calculate the number of even and odd indexed positions based on the length of the string n. We then multiply the number of valid choices for each type of index position to get the total number of good strings.

1. Determine the number of even and odd indexed positions based on n.
2. Calculate the total good strings as:
   • If n is even: 5^(n/2) * 4^(n/2)
   • If n is odd: 5^((n//2) + 1) * 4^(n//2)
3. Return the result modulo 10^9 + 7.

Code Solutions