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, 10¹⁸].
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.

1class Solution {2    public String smallestGoodBase(String n) {3        long numN = Long.parseLong(n);4        // The max number of digits 'm' is for the smallest base k=2.5        // 2^(m-1) <= n  => m-1 <= log2(n) => m <= log2(n) + 16        // For n=10^18, log2(10^18) is approx 59.79. So max m is 60.7        for (int m = 60; m >= 2; m--) {8            long low = 2;9            // Upper bound for k: k^(m-1) < n => k < n^(1/(m-1))10            long high = (long) (Math.pow(numN, 1.0 / (m - 1)) + 1);11 12            while (low <= high) {13                long k = low + (high - low) / 2;14                if (k < 2) {15                    // This can happen if high becomes 1, we should search for k>=216                    low = 2;17                    continue;18                }19                20                long sum = 0;21                long term = 1;22                boolean overflow = false;23                for (int i = 0; i < m; i++) {24                    if (Long.MAX_VALUE - term < sum) {25                        overflow = true;26                        break;27                    }28                    sum += term;29                    if (i < m - 1) {30                        // Check for overflow before multiplication31                        if (term > Long.MAX_VALUE / k) {32                            overflow = true;33                            break;34                        }35                        term *= k;36                    }37                }38 39                if (overflow || sum > numN) {40                    high = k - 1;41                } else if (sum < numN) {42                    low = k + 1;43                } else {44                    return String.valueOf(k);45                }46            }47        }48        // Default case for m=2, k = n-149        return String.valueOf(numN - 1);50    }51}

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.

This approach is an optimization of the binary search method. Instead of searching for the base k for each possible number of digits m, we can directly calculate the only possible integer candidate for k. From the equation n = 1 + k + ... + k^(m-1), we can observe that k^(m-1) < n < (k+1)^(m-1). This implies k < n^(1/(m-1)) < k+1. Therefore, the only integer candidate for the base k is floor(n^(1/(m-1))). We can calculate this candidate using Math.pow and then verify if it's a good base by computing the sum 1 + k + ... + k^(m-1) and checking if it equals n. This eliminates the need for a binary search loop.

Algorithm

Parse the input string n to a long variable, numN.
Iterate through the number of digits m from a maximum possible value (e.g., 60) down to 2.
For each m, calculate the candidate base k using the approximation k ≈ n^(1/(m-1)). The precise integer candidate is k = floor(n^(1/(m-1))). This can be computed using k = (long) Math.pow(numN, 1.0 / (m - 1)).
If the calculated k is less than 2, we can continue to the next m, as a valid base must be at least 2.
Verify if this candidate k is a valid good base. Calculate the sum S = 1 + k + k^2 + ... + k^(m-1).
The sum calculation must be done carefully to avoid long overflow.
If S equals numN, then k is a good base. Since we are iterating m from high to low, this is the smallest good base. Return k as a string.
If the loop completes without finding a solution, the answer corresponds to m=2, where k = n - 1. Return (numN - 1) as a string.

Walkthrough

This method improves upon the previous one by avoiding the binary search. The core mathematical insight is that for a fixed number of digits m, there is at most one integer base k that can satisfy the equation n = 1 + k + ... + k^(m-1). This k can be estimated very accurately. Since n is the sum of a geometric series, n is slightly larger than k^(m-1). This gives the approximation k ≈ n^(1/(m-1)). In fact, it can be shown that the only integer candidate for k is floor(n^(1/(m-1))). So, for each m we iterate through, we calculate this single candidate k and check if it works. The check involves computing the geometric sum and comparing it to n, again being careful about potential overflows. This direct calculation is faster than a full binary search.

1class Solution {2    public String smallestGoodBase(String n) {3        long numN = Long.parseLong(n);4        // Max m is around 60 for n <= 10^185        for (int m = 60; m >= 2; m--) {6            // From n = (k^m - 1) / (k - 1), we have k ≈ n^(1/(m-1))7            long k = (long) Math.pow(numN, 1.0 / (m - 1));8 9            if (k < 2) {10                continue;11            }12 13            // Verify if this k is the correct base14            long sum = 0;15            long term = 1;16            boolean overflow = false;17            for (int i = 0; i < m; i++) {18                if (Long.MAX_VALUE - term < sum) {19                    overflow = true;20                    break;21                }22                sum += term;23                if (i < m - 1) {24                    if (term > Long.MAX_VALUE / k) {25                        overflow = true;26                        break;27                    }28                    term *= k;29                }30            }31 32            if (!overflow && sum == numN) {33                return String.valueOf(k);34            }35        }36        // The trivial case with m=2 digits (11) is always possible.37        // n = k + 1 => k = n - 1. This is the largest possible base.38        return String.valueOf(numN - 1);39    }40}

Complexity

Time

O((log n)^2). The outer loop runs `O(log n)` times (for `m` from `~60` to 2). Inside the loop, calculating the candidate `k` is fast. The verification step involves a loop that runs `m` times. The total time is the sum of `m` for `m` from 2 to `log n`, which is `Σ m ≈ (log n)^2 / 2`. This is asymptotically the same as the binary search approach but with better constant factors.

Space

O(1) extra space. Constant extra space is used for variables.

Trade-offs

Pros

The most efficient approach in practice due to avoiding the binary search loop.
Conceptually simpler than the binary search approach once the mathematical insight is understood.

Cons

Relies on the precision of Math.pow. While it works for the given constraints, for extremely large numbers or different floating-point implementations, it might require checking k-1 or k+1 as well to be fully robust. For this problem's constraints, it is reliable.

Solutions

Solution

1class Solution {2public3  String smallestGoodBase(String n) {4    long num = Long.parseLong(n);5    for (int len = 63; len >= 2; --len) {6      long radix = getRadix(len, num);7      if (radix != -1) {8        return String.valueOf(radix);9      }10    }11    return String.valueOf(num - 1);12  }13private14  long getRadix(int len, long num) {15    long l = 2, r = num - 1;16    while (l < r) {17      long mid = l + r >>> 1;18      if (calc(mid, len) >= num)19        r = mid;20      else21        l = mid + 1;22    }23    return calc(r, len) == num ? r : -1;24  }25private26  long calc(long radix, int len) {27    long p = 1;28    long sum = 0;29    for (int i = 0; i < len; ++i) {30      if (Long.MAX_VALUE - sum < p) {31        return Long.MAX_VALUE;32      }33      sum += p;34      if (Long.MAX_VALUE / p < radix) {35        p = Long.MAX_VALUE;36      } else {37        p *= radix;38      }39    }40    return sum;41  }42}

1class Solution {2public:3  string smallestGoodBase(string n) {4    long v = stol(n);5    int mx = floor(log(v) / log(2));6    for (int m = mx; m > 1; --m) {7      int k = pow(v, 1.0 / m);8      long mul = 1, s = 1;9      for (int i = 0; i < m; ++i) {10        mul *= k;11        s += mul;12      }13      if (s == v) {14        return to_string(k);15      }16    }17    return to_string(v - 1);18  }19};

1class Solution:2    def smallestGoodBase(self, n: str) -> str: def cal(k, m): p = s = 1 for i in range(m): p *= k s += p return s num = int(n) for m in range(63, 1, - 1): l, r = 2, num - 1 while l < r: mid = (l + r) >> 1 if cal(mid, m) >= num: r = mid else: l = mid + 1 if cal(l, m) == num: return str(l) return str(num - 1)

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 problem