1922. Count-Good-Numbers

We want to try to find the number of good numbers of length n where a number is good when the digits at the even position are even and the digits at the odd indices are prime.

We can easily see a pattern here:

• there are 5 valid even position digits (must be even) [0, 2, 4, 6, 8]
• there are 4 valid odd position digits (must be prime) [2, 3, 5, 7]

Therefore, at each position i going from the lowest digit to the highest we have: 4 * 5 * 4 * 5 * ...

If the length of the number if even, we have the same number of even and odd indices and the number of good integers is equal to (5 ** (n / 2)) + (4 ** (n / 2)). If the length of the number if odd, we have the one more odd indices compared to even indices and the number of good integers is equal to (5 ** (n // 2)) + (4 ** (n // 2 + 1))

Therefore, this is a simple calculation problem. However, if we submit the simple arithmetic solution, we are hit with a TLE error due to the exponential explosion that happens (the calculated sum is too large). Therefore, we need to limit the calculated number using the mod provided. To do this, we need to implement our own exponential algorithm that calculates the exponential of a number while restricting the output to output % MOD.

class Solution(object):
    def countGoodNumbers(self, n):
        """
        :type n: int
        :rtype: int
        """
        MOD = 10 ** 9 + 7

        def fast_exp(base, exp):
            res = 1
            curr = base

            while exp > 0:
                if exp % 2 == 1:
                    res = res * curr % MOD
                curr = curr * curr % MOD
                exp //= 2
            return res

        return (fast_exp(20, n // 2) * (5 if n % 2 else 1)) % MO

Time Complexity: O(log n)

Space Complexity: O(1)

Time Taken: 20m 7s