To begin with, the whole problem is equivalent to solving the following equation with smallest `k`

(assuming `k >= 2`

and `m >= 1`

):

`f(k, m) = n`

where `k`

is the base of the numbers, `m`

is the number of digit `1`

's in this base, `f(k, m) = 1 + k + k^2 + ... + k^(m-1) = (k^m - 1)/(k-1)`

is the numeric value of the number in base `10`

, and `n`

is the numeric value of the given input string in base `10`

.

Before we jump into solutions of the equation, let's first dig up some properties of the function `f(k, m) = (k^m - 1)/(k-1)`

.

- If
`m`

is fixed,`f(k, m)`

is monotonically increasing on`k`

. - If
`k`

is fixed,`f(k, m)`

is also monotonically increasing on`m`

.

Now suppose we have two different solutions for the above equation: `(k1, m1)`

and `(k2, m2)`

. Without loss of generality, let's assume `m1 > m2`

, then we can show `k1 < k2`

as follows: `n = f(k2, m2) = f(k1, m1) > f(k1, m2) ==> k2 > k1`

. Similarly for the other case: `m1 < m2 ==> k1 > k2`

. Therefore `k`

and `m`

will be inversely related provided the equation is held true.

The conclusion above suggests that if we can simply find a solution to the equation `f(k, m) = n`

with the largest possible `m`

, then the corresponding `k`

is guaranteed to be the smallest. So now we need to figure out the upper and lower limit on `m`

to impose constraint on our searching range. (Strictly speaking, we may also proceed in the other way round, i.e., to find the smallest `k`

directly but that turns out to be `O(n)`

.)

Note that if the equation is held true, smaller `k`

will correspond to larger `m`

. Since the minimum of `k`

is `2`

, we know the maximum of `m`

will be `log(n + 1)`

(logarithm of `(n+1)`

in base `2`

). What about the lower limit? Note that `n >= 3`

, therefore `m`

cannot be `1`

(otherwise the numeric value would be `1`

and the equation will have no solutions). To summarize, we have: `2 <= m <= log(n + 1)`

.

So our solution will go like this, starting from the upper limit of `m`

, check if we can find a `k`

so that the equation `f(k, m) = n`

is held true. If so, return the corresponding `k`

as the solution. Otherwise decrease the value of `m`

by `1`

and repeat the process until either a solution is found or all values of `m`

have been exhausted. Note that for any `n >= 3`

, there is a trivial solution where `k = n - 1 and m = 2`

, therefore our searching process above is guaranteed to find at least one solution.

The last part is how to find the solution to the equation with `m`

fixed. A straightforward way would be doing binary search. One point worth noting here is the upper and lower limits for the searching range of `k`

. For the upper limit, note that `n = f(k, m) = 1 + k + ... + k^(m-1) > k^(m-1) ==> k < n^(1/(m-1))`

. For the lower limit, note that `n = f(k, m) = (k^m - 1)/(k-1) <= (k^m - 1) ==> k >= (n+1)^(1/m)`

. To summarize: `(n+1)^(1/m) <= k <= n^(1/(m-1))`

.

So here comes our final solution based on the analyses above. Note that the range of the input `n`

is `[3, 10^18]`

, so `n`

can fit into a `long`

type variable. Also if for each `m`

, `k`

is in the searching range specified above, we won't have overflow problem. As for the time complexity, in the worst case, we need to scan the whole range of `m`

, which is O(logn); for each `m`

, the binary search is O(logn) too; therefore our solution will run at O((logn)^2).

```
public String smallestGoodBase(String n) {
long num = Long.valueOf(n);
for (int m = (int)(Math.log(num + 1) / Math.log(2)); m >= 2; m--) {
long l = (long)(Math.pow(num + 1, 1.0 / m));
long r = (long)(Math.pow(num, 1.0 / (m - 1)));
while (l <= r) {
long k = l + ((r - l) >> 1);
long f = 0L;
for (int i = 0; i < m; i++, f = f * k + 1);
if (num == f) {
return String.valueOf(k);
} else if (num < f) {
r = k - 1;
} else {
l = k + 1;
}
}
}
return String.valueOf(num - 1);
}
```