Problem Informations

• Problem Index: 1922
• Problem Link: Count Good Numbers
• Topics: Math, Recursion

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

• 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 $10^9 + 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 \leq n \leq 10^{15}$

Intuition

The problem involves creating digit strings with specific properties at even and odd indices. At even indices, digits must be even, and at odd indices, digits must be prime from the set ${2, 3, 5, 7}$. Given the constraints, we need an efficient way to determine the number of such digit strings without generating them explicitly. The idea is to use combinatorial and modular arithmetic to count the number of valid combinations, leveraging the properties of these digits.

Approach

To solve the problem, we can break down the digit string based on indices:

1. Even Indices: The digits allowed are ${0, 2, 4, 6, 8}$, which gives us 5 choices per even index.
2. Odd Indices: The digits allowed are ${2, 3, 5, 7}$, which gives us 4 choices per odd index.

Given that the string length is $n$, half of the digits (approximately) will fall into even indices and the other half into odd indices.

1. Calculation of Even Positions: The number of positions with even indices is $\lceil n/2 \rceil$. For each of these positions, we have 5 available digits, thus $5^{\lceil n/2 \rceil}$ possible combinations.

2. Calculation of Odd Positions: The number of positions with odd indices is $\lfloor n/2 \rfloor$. For each of these positions, we have 4 available digits, thus $4^{\lfloor n/2 \rfloor}$ possible combinations.

3. Total Combinations: The total number of “good” digit strings is the product of the combinations from even and odd indexed positions, which is $5^{\lceil n/2 \rceil} \times 4^{\lfloor n/2 \rfloor}$.

4. Handling Large $n$: Given that $n$ can be as large as $10^{15}$, directly computing large powers can result in computational and storage challenges. We use fast modular exponentiation to efficiently handle these large powers and ensure the results remain manageable. The final answer must be computed modulo $10^9 + 7$.

The function fast_pow_mod implements fast modular exponentiation, which computes $(\text{base}^\text{exp}) \bmod \text{mod}$ using a method called exponentiation by squaring. This is an efficient O(log exp) method:

• Start with result initially set to 1.
• While the exponent is greater than 0:
  • If the exponent is odd, multiply the current result by the base and take modulo.
  • Square the base and reduce modulo.
  • Divide the exponent by 2 using right shift.

This method ensures that we can handle large exponents even when $n$ is very large. The function countGoodNumbers finally computes the product of the possibilities for even and odd indices and returns the result modulo $10^9 + 7$.

Code

C++

#define MOD (long long)(1e9+7)

class Solution {
private:
    // Function to perform fast modular exponentiation
    long long fast_pow_mod(long long base, long long exp, long long mod) {
        long long result = 1;
        base %= mod; // Reduce base modulo mod at the start
        while (exp > 0) {
            if (exp & 1) { // Check if the current exponent is odd
                result = result * base % mod; // Multiply result by base if exp is odd
            }
            base = base * base % mod; // Square the base
            exp >>= 1; // Right shift exp by 1 (divide it by 2)
        }
        return result;
    }
public:
    // Function to count good digit strings of length n
    int countGoodNumbers(long long n) {
        // Calculate the total number of good digit strings
        // by multiplying the possibilities at even and odd indices
        return (fast_pow_mod(5, (n + 1) / 2, MOD) * fast_pow_mod(4, n / 2, MOD)) % MOD;
    }
};

Python

class Solution:
    # Define the modulo constant
    MOD = int(1e9 + 7)
    
    # Function to perform fast modular exponentiation
    def fast_pow_mod(self, base, exp, mod):
        result = 1
        base %= mod  # Reduce base modulo mod at the start
        while exp > 0:
            if exp & 1:  # Check if the current exponent is odd
                result = result * base % mod  # Multiply result by base if exp is odd
            base = base * base % mod  # Square the base
            exp >>= 1  # Right shift exp by 1 (divide it by 2)
        return result
    
    # Function to count good digit strings of length n
    def countGoodNumbers(self, n):
        # Calculate the total number of good digit strings
        # by multiplying the possibilities at even and odd indices
        return (self.fast_pow_mod(5, (n + 1) // 2, self.MOD) * self.fast_pow_mod(4, n // 2, self.MOD)) % self.MOD

Complexity

• Time complexity: $O(\log n)$

  The core operation in the code is the fast_pow_mod function, which performs fast modular exponentiation. The time complexity of this function is $O(\log \text{exp})$, where exp is the exponent. In this code, it is called twice in countGoodNumbers with exponents $\lceil \frac{n}{2} \rceil$ and $\lfloor \frac{n}{2} \rfloor$, respectively. Since both are approximately $n/2$, the overall time complexity becomes $O(\log n)$.

• Space complexity: $O(1)$

  The space complexity is $O(1)$ because the algorithm requires a constant amount of space that does not depend on the input size $n$. The only local variables used are a few integers for calculations. The recursion depth of the algorithm does not increase with $n$, ensuring constant space usage.