Count Good Numbers

main.md

Question

Approach

I figured out how many positions in the string need even digits and how many need prime digits. I then raised 5 to the power of even positions and 4 to the power of odd positions and multiplied them. Since n can be very large, I used fast exponentiation to keep the computation efficient and within the modulo range.

Implementation

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10**9 + 7
        
        def mod_pow(base, exp):
            result = 1
            while exp > 0:
                if exp % 2 == 1:
                    result = (result * base) % MOD
                base = (base * base) % MOD
                exp //= 2
            return result
        
        even_positions = (n + 1) // 2
        odd_positions = n // 2
        
        return (mod_pow(5, even_positions) * mod_pow(4, odd_positions)) % MOD

Complexities

• Time: O(log n)
• Space: O(1)