# 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;
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0483-smallest-good-base.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.