Smallest Good Base

Hard Binary Search Binary Search on Answer Space Original on LeetCode

Reported atRazorpay

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

  • n is the decimal form of an integer in the range [3, 10^18]
  • n has 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(log³ n)About log n digit counts, each with a binary search of about log n steps, each evaluating up to log n terms.
SpaceO(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).

  1. Parse n as a 64-bit integer.
  2. For m from 62 down to 3: binary search k in [2, n - 1].
  3. 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.
  4. 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);
    }
}

2Optimal (direct root for each digit count)

TimeO(log² n)About log n digit counts, each checking 3 candidates in O(log n) time.
SpaceO(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.

  1. maxM = number of bits of n (since 2^(m-1) <= n).
  2. For m from maxM down to 3: k = floor(n^(1/(m-1))) using floating point.
  3. For cand in k - 1, k, k + 1 (cand >= 2): if 1 + cand + … + cand^(m-1) == n exactly, return cand.
  4. 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;
    }
}

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).