Problem of The Day: Count Good Numbers

Problem Statement

leetcode problem link

Brute Force [TLE]

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10**9 + 7
        res = 1
        even = 5 # {0, 2, 4, 6, 8} choices
        odd = 4 # {2, 3, 5, 7} choices
        for i in range(n):
            if i % 2 == 0:
                res = (res * even)
            else:
                res = (res * odd)

        return res % MOD

Editorial

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        mod = 10**9 + 7

        # use fast exponentiation to calculate x^y % mod
        def quickmul(x: int, y: int) -> int:
            ret, mul = 1, x
            while y > 0:
                if y % 2 == 1:
                    ret = ret * mul % mod
                mul = mul * mul % mod
                y //= 2
            return ret

        return quickmul(5, (n + 1) // 2) * quickmul(4, n // 2) % mod

Given a number n, the goal is to count how many “good numbers” of length n can be formed, where:

Even-indexed positions (0, 2, 4, …) can have any even digit → 5 choices (0, 2, 4, 6, 8)

Odd-indexed positions (1, 3, 5, …) can have any prime digit → 4 choices (2, 3, 5, 7)

How Many Choices? Let’s break it down:

Even positions = (n + 1) // 2

Odd positions = n // 2

So total number of good numbers = 5^(even positions) * 4^(odd positions)