Smallest Good Base Python Solution with Tests

lcpy gen -n 483   # by problem number
lcpy gen -s smallest_good_base   # by problem name

Input: n = "13"
Output: "3"
Explanation: 13 base 3 is 111.

Input: n = "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.

Input: n = "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.

class Solution:
    # Time: O(log^2 n) -- ~60 digit counts, each a binary search over bases
    # Space: O(1)
    def smallest_good_base(self, n: str) -> str:
        num = int(n)
        for m in range(num.bit_length(), 1, -1):
            # candidates for base k with m+1 digits of 1: k ~ num^(1/m)
            lo, hi = 2, round(num ** (1.0 / m)) + 2
            while lo < hi:
                mid = (lo + hi) // 2
                total, power = 0, 1
                overflow = False
                for _ in range(m + 1):
                    total += power
                    if total > num:
                        overflow = True
                        break
                    power *= mid
                if overflow:
                    hi = mid
                elif total == num:
                    return str(mid)
                else:
                    lo = mid + 1
        return str(num - 1)