> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Smallest Good Base Python Solution with Tests

> Tested Python solution for LeetCode 483 with 32 pytest cases. Generate a practice environment with lcpy.

LeetCode 483, [Hard](/catalog/hard). Topics: [Math](/catalog/topics/math), [Binary Search](/catalog/topics/binary-search). [View on LeetCode](https://leetcode.com/problems/smallest-good-base/description/).

Generate this problem as a practice environment: tested reference solution, 32 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 483   # by problem number
lcpy gen -s smallest_good_base   # by problem name
```

## Problem

Given an integer `n` represented as a string, return *the smallest **good base** of* `n`.

We call `k >= 2` a **good base** of `n`, if all digits of `n` base `k` are `1`'s.

### Examples

```
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.
```

### Constraints

* n is an integer in the range \[3, 10^18]
* n does not contain any leading zeros.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/smallest_good_base/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/smallest_good_base/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
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)
```

## Complexity

| Time | Space |
| - | - |
| O(log^2 n) -- \~60 digit counts, each a binary search over bases | O(1) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.