Smallest Good Base — Solution in Python, Java & C++
Smallest Good Base solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Smallest Good Base is a hard coding problem on math, binary search and number theory, asked in Amazon, Google, Apple and Razorpay interviews.
- Difficulty: Hard
- Topics: Math, Binary Search, Number Theory
- Asked at: Amazon, Google, Apple, Razorpay
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A base k >= 2 is good for n if every digit of n written in base k is 1.
Given n as a decimal string, return the smallest good base, also as a string.
Example 1
Input: n = "13"
Output: 3
Explanation: 13 in base 3 is 111.
Example 2
Input: n = "4681"
Output: 8
Explanation: 4681 in base 8 is 11111.
Example 3
Input: n = "3"
Output: 2
Explanation: 3 in base 2 is 11 — every n has base n - 1 as a fallback.
Constraints
3 <= n <= 1000000000n is given without leading zeros.
Hints for Smallest Good Base
Hint 1
If
nis all ones in basekwithm + 1digits, thenn = 1 + k + k² + … + k^m.Hint 2
More digits means a smaller base, so search
mfrom large to small and take the first base that works.Hint 3
For a fixed
mthe sum is increasing ink, so binary searchk— and cap the range by doubling rather than taking a real-valued root.
How to solve Smallest Good Base
An all-ones representation with m + 1 digits means n is the geometric sum 1 + k + … + k^m. That sum grows with k for fixed m, so each m admits at most one base, findable by binary search. Larger m forces smaller k, so scanning m downward returns the smallest base first.
Approach
- For
mfrom30down to1(since2^31already exceeds the input bound): - Find an upper bound for
kby starting at 2 and doubling until the geometric sum reachesn. - Binary search
kin that range, comparing the sum againstn; returnkon an exact hit. - If no
mworks, the answer isn - 1, which always representsnas11.
Why it works
Every n >= 3 is 11 in base n - 1, so a good base always exists. For a fixed digit count the sum is strictly increasing in k, which makes the binary search valid; and the sum is strictly increasing in m for fixed k, so more digits force a smaller base — hence the downward scan finds the minimum first.
Complexity
- Time —
O(log²n) - Space —
O(1)
Pitfalls
- Computing
k^mdirectly overflows long before the sum reachesn— cap the running total againstnat every step. - Using a floating-point
m-th root to boundkcan land one off, and the judge's C harness has nomath.h; doubling avoids both problems. m = 1yieldsn - 1, which is why the search always terminates with an answer.
Reference solution
Python
def smallestGoodBase(n: str) -> str:
v = int(n)
def sum_pow(k: int, m: int, limit: int) -> int:
total = 1
term = 1
for _ in range(m):
if term > limit // k:
return limit + 1
term *= k
if total > limit - term:
return limit + 1
total += term
return total
for m in range(30, 0, -1):
hi = 2
while sum_pow(hi, m, v) < v:
hi *= 2
lo = 2
while lo <= hi:
mid = (lo + hi) // 2
s = sum_pow(mid, m, v)
if s == v:
return str(mid)
if s < v:
lo = mid + 1
else:
hi = mid - 1
return str(v - 1)Java
public static String smallestGoodBase(String n) {
long v = Long.parseLong(n);
for (int m = 30; m >= 1; m--) {
long hi = 2;
while (geoSum(hi, m, v) < v) hi *= 2;
long lo = 2;
while (lo <= hi) {
long mid = (lo + hi) / 2;
long s = geoSum(mid, m, v);
if (s == v) return Long.toString(mid);
if (s < v) lo = mid + 1;
else hi = mid - 1;
}
}
return Long.toString(v - 1);
}
static long geoSum(long k, int m, long limit) {
long sum = 1, term = 1;
for (int i = 1; i <= m; i++) {
if (term > limit / k) return limit + 1;
term *= k;
if (sum > limit - term) return limit + 1;
sum += term;
}
return sum;
}C++
static long long geoSum(long long k, int m, long long limit) {
long long sum = 1, term = 1;
for (int i = 1; i <= m; i++) {
if (term > limit / k) return limit + 1;
term *= k;
if (sum > limit - term) return limit + 1;
sum += term;
}
return sum;
}
string smallestGoodBase(string n) {
long long v = stoll(n);
for (int m = 30; m >= 1; m--) {
long long hi = 2;
while (geoSum(hi, m, v) < v) hi *= 2;
long long lo = 2;
while (lo <= hi) {
long long mid = (lo + hi) / 2;
long long s = geoSum(mid, m, v);
if (s == v) return to_string(mid);
if (s < v) lo = mid + 1;
else hi = mid - 1;
}
}
return to_string(v - 1);
}JavaScript
var smallestGoodBase = function(n) {
var v = Number(n);
var sumPow = function(k, m, limit) {
var sum = 1, term = 1;
for (var i = 1; i <= m; i++) {
if (term > Math.floor(limit / k)) return limit + 1;
term *= k;
if (sum > limit - term) return limit + 1;
sum += term;
}
return sum;
};
for (var m = 30; m >= 1; m--) {
var hi = 2;
while (sumPow(hi, m, v) < v) hi *= 2;
var lo = 2;
while (lo <= hi) {
var mid = Math.floor((lo + hi) / 2);
var s = sumPow(mid, m, v);
if (s === v) return String(mid);
if (s < v) lo = mid + 1;
else hi = mid - 1;
}
}
return String(v - 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Binary Search