Smallest Good Base

Hard
718.

Smallest Good Base

Smallest Good Base is a hard coding problem on math, binary search and number theory, asked in Amazon, Google, Apple and Razorpay interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} n
 * @return {string}
 */
var smallestGoodBase = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Smallest Good Base

  1. Hint 1

    If n is all ones in base k with m + 1 digits, then n = 1 + k + k² + … + k^m.

  2. Hint 2

    More digits means a smaller base, so search m from large to small and take the first base that works.

  3. Hint 3

    For a fixed m the sum is increasing in k, so binary search k — 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

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

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