Scale Engineer

Smallest Good Base

Hard
#0470Time: O((log n)^2). The outer loop runs `O(log n)` times (for `m` from `~60` to 2). For each `m`, we perform a binary search for `k`. The number of binary search steps is `log(n^(1/(m-1))) = (1/(m-1))log(n)`. Inside the binary search, we calculate a sum in `O(m)` time. The total time is the sum over `m`: `Σ [ (log(n)/(m-1)) * m ]` for `m` from 2 to `log n`, which simplifies to `O((log n)^2)`.Space: O(1) extra space. We only use a few variables to store state during the computation.
Patterns
Math
Algorithms
Binary Search

Prompt

Given an integer n represented as a string, return the smallest good base of n.

We call k >= 2 a good base of n, if all digits of n base k are 1's.

 

Example 1:

Input: n = "13"
Output: "3"
Explanation: 13 base 3 is 111.

Example 2:

Input: n = "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.

Example 3:

Input: n = "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.

 

Constraints:

  • n is an integer in the range [3, 1018].
  • n does not contain any leading zeros.

Approaches

2 approaches with complexity analysis and trade-offs.

The core idea is to rephrase the problem. Instead of searching for the base k directly, which can be as large as n-1, we can search for the number of digits m in the base k representation. If n in base k is represented by m ones, the equation is n = 1 + k + k^2 + ... + k^(m-1). The number of digits m is bounded by log2(n), which is at most 60 for n <= 10^18. This small range for m allows us to iterate through all possible values of m. For a fixed m, the equation n = 1 + k + ... + k^(m-1) is monotonic with respect to k. This allows us to use binary search to find the correct integer k. We should iterate m from its maximum possible value down to 2. The first valid (k, m) pair we find will give the smallest k, because a larger m implies a smaller k.

Algorithm

  • Parse the input string n to a long variable, numN.
  • The maximum possible number of digits m occurs when the base k is minimal (i.e., k=2). This gives m <= log2(n) + 1. For n <= 10^18, m is at most 60.
  • Iterate m from 60 down to 2. A larger m implies a smaller base k, so we iterate downwards to find the smallest k first.
  • For each m, perform a binary search for the base k in the range [2, n^(1/(m-1))].
  • In the binary search, for a candidate base mid_k:
    • Calculate the sum S = 1 + mid_k + mid_k^2 + ... + mid_k^(m-1).
    • This sum must be calculated carefully to prevent long overflow. If an overflow occurs, treat the sum as a very large number.
    • If S == numN, we have found a valid base mid_k. Since we are iterating m downwards, this mid_k is the smallest possible good base. Return it as a string.
    • If S < numN, the base mid_k is too small. Search in the upper half: low = mid_k + 1.
    • If S > numN (or overflowed), the base mid_k is too large. Search in the lower half: high = mid_k - 1.
  • If the loop finishes without finding a good base, it means the only solution is for m=2. In this case, n = k + 1, so the base is k = n - 1. Return (numN - 1) as a string.

Walkthrough

This approach tackles the problem by changing the primary variable of iteration. Instead of iterating through all possible bases k from 2 to n-1 (which is infeasible), we iterate through the number of digits, m. The number of digits m is small, ranging from 2 to about 60. For each fixed m, we need to find an integer k that satisfies n = 1 + k + ... + k^(m-1). Since the sum on the right is a monotonically increasing function of k, we can efficiently find k using binary search. The search space for k for a given m is from 2 to n-1, but can be tightly bounded by [2, n^(1/(m-1))]. During the binary search, we must carefully calculate the geometric sum to avoid long integer overflow, as intermediate products can exceed Long.MAX_VALUE. If the calculated sum for a candidate k matches n, we've found a solution. By searching for m from largest to smallest, the first solution found will have the smallest base k.

class Solution {    public String smallestGoodBase(String n) {        long numN = Long.parseLong(n);        // The max number of digits 'm' is for the smallest base k=2.        // 2^(m-1) <= n  => m-1 <= log2(n) => m <= log2(n) + 1        // For n=10^18, log2(10^18) is approx 59.79. So max m is 60.        for (int m = 60; m >= 2; m--) {            long low = 2;            // Upper bound for k: k^(m-1) < n => k < n^(1/(m-1))            long high = (long) (Math.pow(numN, 1.0 / (m - 1)) + 1);             while (low <= high) {                long k = low + (high - low) / 2;                if (k < 2) {                    // This can happen if high becomes 1, we should search for k>=2                    low = 2;                    continue;                }                                long sum = 0;                long term = 1;                boolean overflow = false;                for (int i = 0; i < m; i++) {                    if (Long.MAX_VALUE - term < sum) {                        overflow = true;                        break;                    }                    sum += term;                    if (i < m - 1) {                        // Check for overflow before multiplication                        if (term > Long.MAX_VALUE / k) {                            overflow = true;                            break;                        }                        term *= k;                    }                }                 if (overflow || sum > numN) {                    high = k - 1;                } else if (sum < numN) {                    low = k + 1;                } else {                    return String.valueOf(k);                }            }        }        // Default case for m=2, k = n-1        return String.valueOf(numN - 1);    }}

Complexity

Time

O((log n)^2). The outer loop runs `O(log n)` times (for `m` from `~60` to 2). For each `m`, we perform a binary search for `k`. The number of binary search steps is `log(n^(1/(m-1))) = (1/(m-1))log(n)`. Inside the binary search, we calculate a sum in `O(m)` time. The total time is the sum over `m`: `Σ [ (log(n)/(m-1)) * m ]` for `m` from 2 to `log n`, which simplifies to `O((log n)^2)`.

Space

O(1) extra space. We only use a few variables to store state during the computation.

Trade-offs

Pros

  • Correctly solves the problem for large inputs within the given constraints.

  • Much more efficient than a naive brute-force search over k.

  • Robust against floating-point inaccuracies as it only uses Math.pow to establish a search bound, not for the final answer.

Cons

  • Slightly more complex to implement due to the nested loop structure (iteration + binary search).

  • The binary search adds a logarithmic factor to the complexity for each m, making it slightly slower in practice than the direct calculation approach, although their asymptotic complexities are the same.

Solutions

class Solution {public  String smallestGoodBase(String n) {    long num = Long.parseLong(n);    for (int len = 63; len >= 2; --len) {      long radix = getRadix(len, num);      if (radix != -1) {        return String.valueOf(radix);      }    }    return String.valueOf(num - 1);  }private  long getRadix(int len, long num) {    long l = 2, r = num - 1;    while (l < r) {      long mid = l + r >>> 1;      if (calc(mid, len) >= num)        r = mid;      else        l = mid + 1;    }    return calc(r, len) == num ? r : -1;  }private  long calc(long radix, int len) {    long p = 1;    long sum = 0;    for (int i = 0; i < len; ++i) {      if (Long.MAX_VALUE - sum < p) {        return Long.MAX_VALUE;      }      sum += p;      if (Long.MAX_VALUE / p < radix) {        p = Long.MAX_VALUE;      } else {        p *= radix;      }    }    return sum;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem