Smallest Good Base

hard math binary search

Problem

Given n as a string, return the smallest integer base k ≥ 2 such that n in base k is all 1s.

Inputn = "13"

Output"3"

13 = 1·3² + 1·3 + 1, so 13 in base 3 is "111".

def smallest_good_base(n):
    N = int(n)
    for m in range(int(N.bit_length()), 1, -1):
        k = int(round(N ** (1 / (m - 1))))
        if k < 2: continue
        if sum(k**i for i in range(m)) == N:
            return str(k)
    return str(N - 1)

function smallestGoodBase(n) {
  const N = BigInt(n);
  const bits = N.toString(2).length;
  for (let m = bits; m > 1; m--) {
    const k = BigInt(Math.floor(Math.pow(Number(N), 1 / (m - 1))));
    if (k < 2n) continue;
    let sum = 0n, p = 1n;
    for (let i = 0; i < m; i++) { sum += p; p *= k; }
    if (sum === N) return k.toString();
  }
  return (N - 1n).toString();
}

class Solution {
    public String smallestGoodBase(String n) {
        long N = Long.parseLong(n);
        for (int m = 63; m > 1; m--) {
            long k = (long) Math.pow(N, 1.0 / (m - 1));
            if (k < 2) continue;
            long sum = 0, p = 1;
            for (int i = 0; i < m; i++) { sum += p; p *= k; }
            if (sum == N) return Long.toString(k);
        }
        return Long.toString(N - 1);
    }
}

string smallestGoodBase(string n) {
    long long N = stoll(n);
    for (int m = 63; m > 1; m--) {
        long long k = (long long) pow((double)N, 1.0 / (m - 1));
        if (k < 2) continue;
        long long sum = 0, p = 1;
        for (int i = 0; i < m; i++) { sum += p; p *= k; }
        if (sum == N) return to_string(k);
    }
    return to_string(N - 1);
}

Explanation

"n in base k is all 1s" means n = 1 + k + k² + ... + k^(m-1) for some length m. A longer all-ones representation forces a smaller base, so we look for the largest m first.

For a fixed length m, that geometric sum is dominated by the top term k^(m-1), so the base is approximately k ≈ n^(1/(m-1)). We compute that estimate, then verify it by actually summing k^0 + k^1 + ... + k^(m-1) and checking it equals n.

We try m from about log₂(n) down to 2. The first m whose computed base checks out gives the smallest good base. If nothing matches, the fallback is base n - 1, since n = 1·(n-1) + 1 is always "11" in that base.

Example: n = 13. Trying m = 3 gives k ≈ 13^(1/2) ≈ 3, and indeed 1 + 3 + 9 = 13. So 13 in base 3 is "111" and the answer is "3".

This is efficient because there are only ~60 possible lengths to try, and for each we do one quick sum to verify.

Time: O(log² n) Space: O(1)