{x}
blog image

Count Good Numbers

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).

  • For example, "2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, "3245" is not good because 3 is at an even index but is not even.

Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 109 + 7.

A digit string is a string consisting of digits 0 through 9 that may contain leading zeros.

 

Example 1:

Input: n = 1
Output: 5
Explanation: The good numbers of length 1 are "0", "2", "4", "6", "8".

Example 2:

Input: n = 4
Output: 400

Example 3:

Input: n = 50
Output: 564908303

 

Constraints:

  • 1 <= n <= 1015

Solution Explanation

This problem asks to count the number of "good" digit strings of length n. A good digit string is defined as a string where digits at even indices are even and digits at odd indices are prime (2, 3, 5, or 7).

The solution leverages the fact that the choices for even and odd indices are independent. There are 5 choices for an even index (0, 2, 4, 6, 8), and 4 choices for an odd index (2, 3, 5, 7).

Approach:

  1. Even Indices: If the length n is even, there are n/2 even indices; if n is odd, there are (n+1)/2 even indices. For each even index, there are 5 choices (0, 2, 4, 6, 8).

  2. Odd Indices: If the length n is even, there are n/2 odd indices; if n is odd, there are (n-1)/2 odd indices. For each odd index, there are 4 choices (2, 3, 5, 7).

  3. Total Combinations: The total number of good strings is the product of the number of choices for even indices and the number of choices for odd indices. Since the numbers can get very large, we use modular arithmetic to prevent overflow.

Code Explanation (Python):

The Python code directly implements this approach using concise bitwise operations:

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
  • (n + 1) >> 1: This is equivalent to (n + 1) // 2, giving the number of even indices (or the number of indices when n is odd, and rounded up) using bitwise right shift.
  • n >> 1: This is equivalent to n // 2, giving the number of odd indices.
  • pow(5, (n + 1) >> 1, mod): This calculates 5(number of even indices) modulo mod.
  • pow(4, n >> 1, mod): This calculates 4(number of odd indices) modulo mod.
  • The final result is the product of these two, taken modulo mod.

Code Explanation (Java, C++, Go):

The Java, C++, and Go codes follow the same logic but explicitly implement the modular exponentiation (myPow) function. This is because the built-in pow function may not directly support modular exponentiation, which is crucial for handling large numbers efficiently and avoiding overflow. The myPow function uses a binary exponentiation method to compute xn mod m efficiently in O(log n) time.

Time Complexity: O(log n) - due to the binary exponentiation used in myPow. The rest of the operations are constant time.

Space Complexity: O(1) - constant extra space is used.