_1922. Count Good Numbers.md

1922. Count Good Numbers

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : April 13, 2025

Last updated : April 13, 2025

---

Related Topics : Math, Recursion

Acceptance Rate : 56.46 %

---

Solutions

• m1922 v1.py
• m1922 v2 cleaned.py

Python

m1922 v1.py

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        mod_val = 10 ** 9 + 7
        # evens
        evens = 1
        tot_cases = (n // 2) + (n % 2)
        prev = []
        if tot_cases > 0 :
            evens = 5
            x = 1
            while 2 * x <= tot_cases :
                prev.append((x, evens))
                evens = (evens * evens) % mod_val
                x *= 2
            while prev :
                i, pow5 = prev.pop()
                if x + i <= tot_cases :
                    x += i
                    evens *= pow5
        
        # odds
        odds = 1
        tot_cases = (n // 2)
        prev = []
        if tot_cases > 0 :
            odds = 4
            x = 1
            while 2 * x <= tot_cases :
                prev.append((x, odds))
                odds = (odds * odds) % mod_val
                x *= 2
            while prev :
                i, pow4 = prev.pop()
                if x + i <= tot_cases :
                    x += i
                    odds *= pow4


        return (evens * odds) % (mod_val)

m1922 v2 cleaned.py

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        def _helper(tot_cases: int, poww: int, mod_val: int = 10 ** 9 + 7) :
            if tot_cases == 0 :
                return 1
            output, x = poww, 1
            prev = []
            while 2 * x <= tot_cases :
                prev.append((x, output))
                output = (output * output) % mod_val
                x *= 2
            while prev :
                i, poww = prev.pop()
                if x + i <= tot_cases :
                    x += i
                    output = (output * poww) % mod_val
            return output

        mod_val = 10 ** 9 + 7
        return (
            _helper((n // 2) + (n % 2), 5, mod_val) * 
            _helper((n // 2), 4, mod_val)
        ) % (mod_val)