Smallest Good Base — Hard Problem & Solution

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.

Difficulty: Hard
Topics: Math, Binary Search, Number Theory
Asked at: Amazon, Google, Apple
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 <= 1000000000
n is given without leading zeros.

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 m from 30 down to 1 (since 2^31 already exceeds the input bound):
Find an upper bound for k by starting at 2 and doubling until the geometric sum reaches n.
Binary search k in that range, comparing the sum against n; return k on an exact hit.
If no m works, the answer is n - 1, which always represents n as 11.

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^m directly overflows long before the sum reaches n — cap the running total against n at every step.
Using a floating-point m-th root to bound k can land one off, and the judge's C harness has no math.h; doubling avoids both problems.
m = 1 yields n - 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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue