## Algorithm

Problem Name: 483. Smallest Good Base

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.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const smallestGoodBase = function(n) {
const N = BigInt(n),
bigint2 = BigInt(2),
bigint1 = BigInt(1),
bigint0 = BigInt(0)
let maxLen = countLength(N, bigint2)
for (let length = maxLen; length > 0; length--) {
let [found, base] = findMatchInHalf(length)
if (found) return '' + base
}
return '' + (N - 1)
function findMatchInHalf(length, smaller = bigint2, bigger = N) {
if (smaller > bigger) return [false]
if (smaller === bigger) {
return [valueOf1s(smaller, length) === N, smaller]
}
let mid = (smaller + bigger) / bigint2
let val = valueOf1s(mid, length)
if (val === N) return [true, mid]
if (val > N) return findMatchInHalf(length, smaller, mid - bigint1)
return findMatchInHalf(length, mid + bigint1, bigger)
}
function valueOf1s(base, lengthOf1s) {
let t = bigint1
for (let i = 1; i < lengthOf1s; i++) {
t *= base
t += bigint1
}
return t
}
function countLength(N, base) {
let t = N,
len = 0
while (t > bigint0) {
t /= base
len++
}
return len
}
}
``````
Copy The Code &

Input

cmd
n = "13"

Output

cmd
"3"

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def smallestGoodBase(self, n):
n = int(n)
for m in range(int(math.log(n, 2)), 1, -1):
k = int(n ** m ** -1)
if (k ** (m + 1) -1) // (k - 1) == n:
return str(k)
return str(n-1)
``````
Copy The Code &

Input

cmd
n = "13"

Output

cmd
"3"