[Leetcode] 1922. Count Good Numbers

https://leetcode.com/problems/count-good-numbers/description/?envType=daily-question&envId=2025-04-13

initial

very straightforward q but i get stack overflow error when trying to compute all possible combinations

wrong or like stack overflow error

import math
class Solution:
    def countGoodNumbers(self, n: int) -> int:
        if n==1:
            return 5
        half = n//2
        if n%2==1:
            return 5**(half+1) * 4**half
        else:
            return 5**half * 4**half

solution

we need to use mod to reduce the value of computation along the way and also this pow() method is powerful to calc the exponent of something whilst moduloing it.

btw very impt to declare mod properly

https://velog.io/@whitehousechef/Number-Float-in-Python

but there is even better way of binary cacl

worse:

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

best with binary: tbc i dont get

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

        def power(base, exp):
            res = 1
            base %= MOD
            while exp > 0:
                if exp % 2 == 1:
                    res = (res * base) % MOD
                base = (base * base) % MOD
                exp //= 2
            return res

        if n == 1:
            return 5

        half = n // 2
        if n % 2 == 1:
            return (power(5, half + 1) * power(4, half)) % MOD
        else:
            return (power(5, half) * power(4, half)) % MOD

complexity