# LeetCode 483: Smallest Good Base

## Problem Restatement

We are given an integer `n` as a string.

We need to return the smallest base `k` such that the representation of `n` in base `k` contains only digit `1`.

For example:

```text
13 in base 3 = 111
```

because:

```text
13 = 1 * 3^2 + 1 * 3^1 + 1 * 3^0
```

So for `n = "13"`, the answer is:

```python
"3"
```

A good base must satisfy `k >= 2`. The problem asks for the smallest such base. The examples include `13 -> 3`, `4681 -> 8`, and `1000000000000000000 -> 999999999999999999`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `n` representing an integer |
| Output | The smallest good base as a string |
| Good base | A base `k >= 2` where every digit of `n` in base `k` is `1` |
| Constraint idea | `n` can be very large, up to around `10^18` |

Function shape:

```python
def smallestGoodBase(n: str) -> str:
    ...
```

## Examples

Example 1:

```python
n = "13"
```

In base `3`:

```text
13 = 1 * 3^2 + 1 * 3^1 + 1
   = 9 + 3 + 1
   = 13
```

Answer:

```python
"3"
```

Example 2:

```python
n = "4681"
```

In base `8`:

```text
4681 = 1 + 8 + 8^2 + 8^3 + 8^4
     = 1 + 8 + 64 + 512 + 4096
     = 4681
```

Answer:

```python
"8"
```

Example 3:

```python
n = "1000000000000000000"
```

The answer is:

```python
"999999999999999999"
```

because in base `999999999999999999`, the number is:

```text
11
```

## First Thought: Try Every Base

The direct idea is to try every base `k` from `2` to `n - 1`.

For each base, repeatedly divide `n` by `k` and check whether every digit is `1`.

This is correct, but impossible for large `n`.

For example, if `n = 10^18`, checking bases one by one would mean almost `10^18` candidates.

We need to search more mathematically.

## Key Insight

If `n` is written as all ones in base `k`, then it has this form:

```text
n = 1 + k + k^2 + k^3 + ... + k^m
```

Here, `m + 1` is the number of digits.

So the problem becomes:

Find the smallest integer `k >= 2` such that:

```text
n = 1 + k + k^2 + ... + k^m
```

for some integer `m >= 1`.

This is a geometric series.

For a fixed `m`, the sum grows as `k` grows. That means we can binary search for `k`.

To get the smallest base, we should try the longest possible representation first.

A longer representation means more digits of `1`, which usually requires a smaller base.

For example:

```text
13 = 111 base 3
13 = 11 base 12
```

Both are valid good bases, but `3` is smaller than `12`.

So we test larger digit counts first.

## Algorithm

Convert `n` to an integer:

```python
num = int(n)
```

The longest possible representation happens in base `2`.

So the maximum possible exponent `m` is roughly:

```python
num.bit_length() - 1
```

Then loop from large `m` down to `1`.

For each `m`, we try to find a base `k` such that:

```text
1 + k + k^2 + ... + k^m = num
```

For each fixed `m`:

1. Set `left = 2`.
2. Set `right` near the `m`-th root of `num`.
3. Binary search for `k`.
4. Compute the geometric sum carefully.
5. If the sum equals `num`, return `k`.

If nothing works, return:

```python
str(num - 1)
```

This always works because:

```text
num = 1 + (num - 1)
```

So in base `num - 1`, the representation is `"11"`.

## Correctness

If `k` is a good base for `num`, then every digit is `1`.

Therefore, for some exponent `m >= 1`:

```text
num = 1 + k + k^2 + ... + k^m
```

So every valid answer appears in the search over possible `m`.

For a fixed `m`, the function:

```text
f(k) = 1 + k + k^2 + ... + k^m
```

strictly increases as `k` increases for all `k >= 2`.

Therefore, binary search can correctly determine whether there is an integer base `k` that gives exactly `num`.

The algorithm checks `m` from largest to smallest. A larger `m` means more digits. For the same number, more digits require a smaller base. Therefore, the first valid base found is the smallest good base.

If no representation with at least three digits exists, the two-digit representation always exists:

```text
num = 1 * (num - 1) + 1
```

So `num - 1` is a valid good base. Returning it is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O((log n)^3)` | There are `O(log n)` possible lengths, each binary search has `O(log n)` steps, and each sum costs `O(log n)` multiplications |
| Space | `O(1)` | Only integer variables are used |

Since `n <= 10^18`, this is very fast.

## Implementation

```python
class Solution:
    def smallestGoodBase(self, n: str) -> str:
        num = int(n)

        max_m = num.bit_length() - 1

        for m in range(max_m, 0, -1):
            left = 2
            right = int(num ** (1 / m)) + 1

            while left <= right:
                k = (left + right) // 2

                total = 1
                power = 1

                for _ in range(m):
                    power *= k
                    total += power

                    if total > num:
                        break

                if total == num:
                    return str(k)

                if total < num:
                    left = k + 1
                else:
                    right = k - 1

        return str(num - 1)
```

## Code Explanation

First, convert the input string:

```python
num = int(n)
```

The input is a string because it may be large, but Python can handle it as an integer.

This finds the largest possible exponent count:

```python
max_m = num.bit_length() - 1
```

If base is `2`, the sum grows slowest, so base `2` gives the longest possible all-ones representation.

Then we try larger digit counts first:

```python
for m in range(max_m, 0, -1):
```

For each `m`, we binary search the base:

```python
left = 2
right = int(num ** (1 / m)) + 1
```

The base cannot be much larger than the `m`-th root of `num`, because the term `k^m` is already part of the sum.

For each candidate base `k`, compute:

```python
total = 1
power = 1

for _ in range(m):
    power *= k
    total += power
```

This builds:

```text
1 + k + k^2 + ... + k^m
```

We stop early if the sum becomes too large:

```python
if total > num:
    break
```

If the sum equals `num`, then `k` is a good base:

```python
if total == num:
    return str(k)
```

If the sum is too small, we need a larger base.

If the sum is too large, we need a smaller base.

The fallback is:

```python
return str(num - 1)
```

This corresponds to representation `"11"`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.smallestGoodBase("13") == "3"
    assert s.smallestGoodBase("4681") == "8"
    assert s.smallestGoodBase("1000000000000000000") == "999999999999999999"
    assert s.smallestGoodBase("3") == "2"
    assert s.smallestGoodBase("7") == "2"
    assert s.smallestGoodBase("15") == "2"
    assert s.smallestGoodBase("21") == "4"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"13"` | Main example: `111` in base `3` |
| `"4681"` | Main example: `11111` in base `8` |
| `"1000000000000000000"` | Large fallback-style case |
| `"3"` | `3 = 11` in base `2` |
| `"7"` | `7 = 111` in base `2` |
| `"15"` | `15 = 1111` in base `2` |
| `"21"` | `21 = 111` in base `4` |