Problem

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.

Examples

Example 1:

1
2
3

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

Example 2:

1
2

Input: n = 4
Output: 400

Example 3:

1
2

Input: n = 50
Output: 564908303

Constraints:

  • 1 <= n <= 10^15

Solution

The problem involves finding the total count of “good” digit strings of length n where a digit string is considered “good” if it satisfies:

  1. Digits at even indices (0, 2, …) are even (0, 2, 4, 6, 8).
  2. Digits at odd indices (1, 3, …) are prime (2, 3, 5, 7).

The constraints allow us to compute the count efficiently using dynamic programming or mathematical calculations.

Method 1 - Using DP

So,

  • A digit at an even index has 5 possible choices: 0, 2, 4, 6, 8.
  • A digit at an odd index has 4 possible choices: 2, 3, 5, 7.

The total number of “good” digit strings can be determined by:

  • Using the combination 5^(ceil(n / 2)) for digits at even positions.
  • Using the combination 4^(floor(n / 2)) for digits at odd positions.

Combining these, the formula is:

1

Total Good Strings = (5^(count_even_indices) * 4^(count_odd_indices)) % MOD

where:

  • count_even_indices = ceil(n / 2) — the number of even positions.
  • count_odd_indices = floor(n / 2) — the number of odd positions.
  • MOD = 10^9 + 7 is used to prevent overflow.

Steps

  1. Compute the number of even and odd indices based on n.
  2. Efficiently calculate modular exponentiation for 5^(count_even_indices) and 4^(count_odd_indices).
  3. Multiply the results and return modulo 10^9 + 7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {

    private static final int MOD = 1_000_000_007;

    public int countGoodNumbers(long n) {
        long countEven = (n + 1) / 2; // ceil(n / 2)
        long countOdd = n / 2; // floor(n / 2)

        long evenCombinations = modExp(5, countEven, MOD);
        long oddCombinations = modExp(4, countOdd, MOD);

        return (int) ((evenCombinations * oddCombinations) % MOD);
    }

    private long modExp(long base, long exp, int mod) {
        long res = 1;
        while (exp > 0) {
            if (exp % 2 == 1) { // If exp is odd
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def countGoodStrings(self, n: int) -> int:
        MOD: int = 1_000_000_007
        
        def mod_exp(base: int, exp: int, mod: int) -> int:
            res: int = 1
            while exp > 0:
                if exp % 2 == 1:  # If exp is odd
                    res = (res * base) % mod
                base = (base * base) % mod
                exp //= 2
            return res
        
        count_even: int = (n + 1) // 2  # ceil(n / 2)
        count_odd: int = n // 2        # floor(n / 2)
        
        even_combinations: int = mod_exp(5, count_even, MOD)
        odd_combinations: int = mod_exp(4, count_odd, MOD)
        
        ans: int = (even_combinations * odd_combinations) % MOD
        return ans

Complexity

  • ⏰ Time complexity: O(log n)
    • Calculating modular exponentiation ( pow(base, exp, MOD) in Python or Math.pow in Java) takes O(log(exp)).
    • Thus, the total time complexity is O(log(n)) because exp depends on n.
  • 🧺 Space complexity: O(1)