Smallest Good Base
Smallest Good Base is a hard binary search problem solved with the binary search on answer space pattern.
The best approach, optimal (direct root for each digit count), runs in O(log² n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (binary search the base for each digit count) up.
Problem
You are given a positive integer n as a decimal string. A base k >= 2 is called good for n if writing n in base k produces only the digit 1 (for example 111 or 11111).
Return the smallest good base of n, also as a decimal string.
Examples
Example 1
- Input
n = "21"- Output
"4"- Why
- 21 = 1 + 4 + 16, so in base 4 it is written 111. Bases 2 and 3 give 10101 and 210.
Example 2
- Input
n = "40"- Output
"3"- Why
- 40 = 1 + 3 + 9 + 27, which is 1111 in base 3; base 2 gives 101000.
Example 3
- Input
n = "1000000000000000000"- Output
"999999999999999999"- Why
- No base below n - 1 writes this number with only 1s, and every n is 11 in base n - 1.
Constraints
nis the decimal form of an integer in the range[3, 10^18]nhas no leading zeros
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (binary search the base for each digit count) | O(log³ n) | O(1) |
| Optimal (direct root for each digit count) | O(log² n) | O(1) |
1Brute force (binary search the base for each digit count)
O(log³ n)About log n digit counts, each with a binary search of about log n steps, each evaluating up to log n terms.O(1)Only a few 64-bit variables.Let m be the number of 1 digits. For m from the largest possible value down to 3, binary search the base k in [2, n - 1]: the value 1 + k + … + k^(m-1) increases with k, so compare it with n while stopping early if it would exceed n (this avoids overflow). The first match is the smallest base, because more digits always mean a smaller base. If nothing matches, the answer is n - 1 (two digits, 11).
- Parse n as a 64-bit integer.
- For m from 62 down to 3: binary search k in [2, n - 1].
- compare(k, m): build sum = 1, cur = 1; for each next digit, if cur > (n - sum) / k the sum is already too big; else cur *= k, sum += cur.
- Return k on an exact match; after all m, return n - 1.
class Solution {
public String smallestGoodBase(String n) {
long num = Long.parseLong(n);
for (int m = 62; m >= 3; m--) {
long lo = 2, hi = num - 1;
while (lo <= hi) {
long k = lo + (hi - lo) / 2;
int c = compare(k, m, num);
if (c == 0) return Long.toString(k);
if (c < 0) lo = k + 1;
else hi = k - 1;
}
}
return Long.toString(num - 1);
}
// compares 1 + k + ... + k^(m-1) with num without overflowing
private int compare(long k, int m, long num) {
long sum = 1, cur = 1;
for (int t = 1; t < m; t++) {
if (cur > (num - sum) / k) return 1;
cur *= k;
sum += cur;
}
return Long.compare(sum, num);
}
}class Solution:
def smallestGoodBase(self, n: str) -> str:
num = int(n)
def compare(k: int, m: int) -> int:
total, cur = 1, 1
for _ in range(m - 1):
cur *= k
total += cur
if total > num:
return 1
return 0 if total == num else -1
for m in range(62, 2, -1):
lo, hi = 2, num - 1
while lo <= hi:
k = (lo + hi) // 2
c = compare(k, m)
if c == 0:
return str(k)
if c < 0:
lo = k + 1
else:
hi = k - 1
return str(num - 1)class Solution {
public:
string smallestGoodBase(string n) {
long long num = stoll(n);
for (int m = 62; m >= 3; m--) {
long long lo = 2, hi = num - 1;
while (lo <= hi) {
long long k = lo + (hi - lo) / 2;
int c = compare(k, m, num);
if (c == 0) return to_string(k);
if (c < 0) lo = k + 1;
else hi = k - 1;
}
}
return to_string(num - 1);
}
private:
// compares 1 + k + ... + k^(m-1) with num without overflowing
int compare(long long k, int m, long long num) {
long long sum = 1, cur = 1;
for (int t = 1; t < m; t++) {
if (cur > (num - sum) / k) return 1;
cur *= k;
sum += cur;
}
return sum == num ? 0 : (sum < num ? -1 : 1);
}
};function smallestGoodBase(n) {
const num = BigInt(n);
// compares 1 + k + ... + k^(m-1) with num (BigInt keeps it exact)
function compare(k, m) {
let sum = 1n, cur = 1n;
for (let t = 1; t < m; t++) {
cur *= k;
sum += cur;
if (sum > num) return 1;
}
return sum === num ? 0 : -1;
}
for (let m = 62; m >= 3; m--) {
let lo = 2n, hi = num - 1n;
while (lo <= hi) {
const k = (lo + hi) / 2n;
const c = compare(k, m);
if (c === 0) return k.toString();
if (c < 0) lo = k + 1n;
else hi = k - 1n;
}
}
return (num - 1n).toString();
}2Optimal (direct root for each digit count)
O(log² n)About log n digit counts, each checking 3 candidates in O(log n) time.O(1)Only a few 64-bit variables.If n has m ones in base k, then k^(m-1) < n < (k + 1)^(m-1), so k must equal the floor of the (m-1)-th root of n. For each m from the bit length of n down to 3, compute that root with floating point, then check it (and its neighbours, to absorb rounding error) exactly with the overflow-safe digit sum. The first hit is the answer; otherwise return n - 1.
- maxM = number of bits of n (since 2^(m-1) <= n).
- For m from maxM down to 3: k = floor(n^(1/(m-1))) using floating point.
- For cand in k - 1, k, k + 1 (cand >= 2): if 1 + cand + … + cand^(m-1) == n exactly, return cand.
- Return n - 1.
class Solution {
public String smallestGoodBase(String n) {
long num = Long.parseLong(n);
int maxM = 64 - Long.numberOfLeadingZeros(num);
for (int m = maxM; m >= 3; m--) {
long k = (long) Math.pow(num, 1.0 / (m - 1));
for (long cand = k - 1; cand <= k + 1; cand++) {
if (cand >= 2 && isAllOnes(cand, m, num)) return Long.toString(cand);
}
}
return Long.toString(num - 1);
}
// true if 1 + k + ... + k^(m-1) == num, stopping before any overflow
private boolean isAllOnes(long k, int m, long num) {
long sum = 1, cur = 1;
for (int t = 1; t < m; t++) {
if (cur > (num - sum) / k) return false;
cur *= k;
sum += cur;
}
return sum == num;
}
}class Solution:
def smallestGoodBase(self, n: str) -> str:
num = int(n)
def is_all_ones(k: int, m: int) -> bool:
total, cur = 1, 1
for _ in range(m - 1):
cur *= k
total += cur
if total > num:
return False
return total == num
for m in range(num.bit_length(), 2, -1):
k = int(num ** (1.0 / (m - 1)))
for cand in (k - 1, k, k + 1):
if cand >= 2 and is_all_ones(cand, m):
return str(cand)
return str(num - 1)class Solution {
public:
string smallestGoodBase(string n) {
long long num = stoll(n);
int maxM = 64 - __builtin_clzll((unsigned long long)num);
for (int m = maxM; m >= 3; m--) {
long long k = (long long)pow((double)num, 1.0 / (m - 1));
for (long long cand = k - 1; cand <= k + 1; cand++) {
if (cand >= 2 && isAllOnes(cand, m, num)) return to_string(cand);
}
}
return to_string(num - 1);
}
private:
// true if 1 + k + ... + k^(m-1) == num, stopping before any overflow
bool isAllOnes(long long k, int m, long long num) {
long long sum = 1, cur = 1;
for (int t = 1; t < m; t++) {
if (cur > (num - sum) / k) return false;
cur *= k;
sum += cur;
}
return sum == num;
}
};function smallestGoodBase(n) {
const num = BigInt(n);
// exact check with BigInt: 1 + k + ... + k^(m-1) == num
function isAllOnes(k, m) {
let sum = 1n, cur = 1n;
for (let t = 1; t < m; t++) {
cur *= k;
sum += cur;
if (sum > num) return false;
}
return sum === num;
}
const maxM = num.toString(2).length;
for (let m = maxM; m >= 3; m--) {
const k = BigInt(Math.floor(Math.pow(Number(num), 1 / (m - 1))));
for (let cand = k - 1n; cand <= k + 1n; cand++) {
if (cand >= 2n && isAllOnes(cand, m)) return cand.toString();
}
}
return (num - 1n).toString();
}Edge cases to test
- Base n - 1 always works (n = 1·(n - 1) + 1), so an answer always exists
- Numbers of the form 2^m - 1 have answer 2
- Values near 10^18 overflow 64-bit integers if the digit sum is computed carelessly
- Perfect cases like 1 + k + k² where k is large (around 10^9)
Hints
Hint 1
If n is written as m ones in base k, then n = 1 + k + k² + … + k^(m-1). Since k >= 2, m is at most about 60.
Hint 2
Fix m. The sum grows with k, so you can binary search k. Try larger m first: more digits means a smaller base.
Hint 3
For a fixed m, n is just above k^(m-1) and below (k+1)^(m-1), so k is the floor of the (m-1)-th root of n. Check that single candidate.
FAQ
What is the best time complexity for Smallest Good Base?
Optimal (direct root for each digit count) runs in O(log² n) time and O(1) extra space. About log n digit counts, each checking 3 candidates in O(log n) time.
Which pattern does Smallest Good Base use?
It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.
Is there a brute force solution for Smallest Good Base?
Yes. Brute force (binary search the base for each digit count) takes O(log³ n) time and O(1) space. Let m be the number of 1 digits.
Which edge cases should I test for Smallest Good Base?
Base n - 1 always works (n = 1·(n - 1) + 1), so an answer always exists; Numbers of the form 2^m - 1 have answer 2; Values near 10^18 overflow 64-bit integers if the digit sum is computed carelessly; Perfect cases like 1 + k + k² where k is large (around 10^9).