# Smallest Good Base
**Difficulty:** HARD
[External](https://leetcode.com/problems/smallest-good-base)
Canonical: https://scaleengineer.com/dsa/problems/smallest-good-base
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
---
## Problem
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
## Iterating on Length and Binary Searching for Base
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`.
**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.
**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.
### Explanation
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`.

```java
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);
    }
}
```
### 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.

## Iterating on Length and Direct Mathematical Calculation
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public String smallestGoodBase(String n) {
        long numN = Long.parseLong(n);
        // Max m is around 60 for n <= 10^18
        for (int m = 60; m >= 2; m--) {
            // From n = (k^m - 1) / (k - 1), we have k ≈ n^(1/(m-1))
            long k = (long) Math.pow(numN, 1.0 / (m - 1));

            if (k < 2) {
                continue;
            }

            // Verify if this k is the correct base
            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) {
                    if (term > Long.MAX_VALUE / k) {
                        overflow = true;
                        break;
                    }
                    term *= k;
                }
            }

            if (!overflow && sum == numN) {
                return String.valueOf(k);
            }
        }
        // The trivial case with m=2 digits (11) is always possible.
        // n = k + 1 => k = n - 1. This is the largest possible base.
        return String.valueOf(numN - 1);
    }
}
```
### 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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  string smallestGoodBase(string n) {
    long v = stol(n);
    int mx = floor(log(v) / log(2));
    for (int m = mx; m > 1; --m) {
      int k = pow(v, 1.0 / m);
      long mul = 1, s = 1;
      for (int i = 0; i < m; ++i) {
        mul *= k;
        s += mul;
      }
      if (s == v) {
        return to_string(k);
      }
    }
    return to_string(v - 1);
  }
};

```

### Python

```python
class Solution:
    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)

```