Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The digit restrictions are independent at each position. Even indices allow five even digits, including zero, while odd indices allow the four prime digits 2, 3, 5, and 7. Multiplying the independent choice counts gives the total.

Approach

There are ceil(n / 2) even-indexed positions and floor(n / 2) odd-indexed positions. Compute 5^ceil(n/2) and 4^floor(n/2) with modular exponentiation, multiply them, and reduce modulo 10^9 + 7. Leading zeros are allowed for these digit strings, so the first position has the same five choices as every other even index. Fast exponentiation supports the very large length bound.

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10**9+7
        odd = n // 2
        even = (n + 1) // 2
        return pow(5, even, MOD) * pow(4, odd, MOD) % MOD

Complexity analysis

Time: O(log n) for modular exponentiation. Auxiliary space: O(1).