DEV Community

Abhishek Chaudhary

Posted on

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.

SOLUTION:

``````class Solution:
def getNum(self, base, l):
val = 0
for _ in range(l):
val = base * val + 1
return val

def smallestGoodBase(self, n: str) -> str:
n = int(n)
for l in range(len("{:b}".format(n)), 1, -1):
beg = 2
end = n - 1
while beg <= end:
mid = (beg + end) // 2
val = self.getNum(mid, l)
if val == n:
return str(mid)
elif beg == end:
break
elif val < n:
beg = mid + 1
else:
end = mid
``````