> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0483-smallest-good-base.md).

# 0483. Smallest Good Base

<https://leetcode.com/problems/smallest-good-base>

## Description

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.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

* `n` is an integer in the range `[3, 1018]`.
* `n` does not contain any leading zeros.

## ac

```java
class Solution {
    public String smallestGoodBase(String n) {
        long num = Long.parseLong(n);
        int maxLen = (int) (Math.log(num + 1) / Math.log(2));
        for (int len = maxLen; len >= 0; len--) {
            long l = 2, r = (long) Math.pow(num, 1.0 / (len-1)) + 1;
            while (l < r) {
                long mid = l + (r-l)/2;
                long sum = 0;
                for (int i = 0; i < len; i++) sum = sum * mid + 1;

                if (sum == num) return ""+mid;
                else if (sum < num) l = mid + 1;
                else r = mid;
            }
        }

        return String.valueOf(num - 1);
    }
}

/*
1) every bit is 1, the length range is [2, log(n+1)/log2], for each length do binary search, from max to min, because max lenght leads to smaller base; 2) base range: [2, pow(n, 1.0/(len-1)) + 1], don't understand why it's the upper, binary search to find the base; 2) every bit is 1, so with candidate base and bits, calculate if it equals n;
*/
```