# Smallest Good Base LeetCode Solution

Here, We see Smallest Good Base LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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.

## Smallest Good Base Solution C++

``````class Solution {
public:
string smallestGoodBase(string n) {
typedef unsigned long long ll;
ll num = stol(n);
for (ll p = log(num+1) / log(2); p >= 2; --p) {
ll lk = 2, rk = pow(num, 1.0 / (p-1))+1;
while (lk <= rk) {
ll mk = lk + (rk - lk) / 2, sum = 0;
for (ll i = 0, f = 1; i < p; ++i, f *= mk)
sum += f;
if (sum < num) lk = mk+1;
else if (sum > num) rk = mk-1;
}
}
}
};```Code language: PHP (php)```

## Smallest Good Base Solution Java

``````class Solution {
public String smallestGoodBase(String n) {
long tn = Long.parseLong(n);
long x = 1;
for (int i = 62; i >= 1; i--) {
if ((x << i) < tn) {
long cur = mySolve(tn, i);
if (cur != 0) {
return Long.toString(cur);
}
}
}
return Long.toString(tn - 1);
}

private long mySolve(long n, int d) {
double tn = (double) n;
long right = (long) (Math.pow(tn, 1.0 / d) + 1);
long left = 1;
while (left <= right) {
long mid = left + (right - left) / 2;
long sum = 1, cur = 1;
for (int i = 1; i <= d; i++) {
cur *= mid;
sum += cur;
}
if (sum == n) {
return mid;
}
if (sum > n) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return 0;
}
}```Code language: JavaScript (javascript)```

## Smallest Good Base Solution JavaScript

``````var smallestGoodBase = function (n) {
n = BigInt(n);
let compute = (base, len) => (base ** BigInt(len) - 1n) / (base - 1n);
for (let len = BigInt(Math.floor(Math.log2(Number(n))) + 1); len >= 2n; len--) {
let low = 2n, high = n;
while (low <= high) {
let mid = (low + high) / 2n;
let sum = compute(mid, len);
if (sum === n) {
return mid.toString();
} else if (sum < n) {
low = mid + 1n;
} else {
high = mid - 1n;
}
}
}
return (n - 1n).toString();
};```Code language: JavaScript (javascript)```

## Smallest Good Base Solution Python

``````class Solution(object):
def smallestGoodBase(self, n):
s=1
ans = []
n = int(n)
while(s<65):
l=2
h=10**18
res = -1
while(l<=h):
mid=(l+h)//2
p = (mid**s - 1)//(mid-1)
if p == n:
res = mid
h = mid - 1
else:
if p>n:
h = mid - 1
else:
l = mid + 1
if res!=-1:
ans.append(res)
s+=1
return str(min(ans))``````
Scroll to Top