# Java O((logn)^2) binary search solution

• 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)`.

1. If `m` is fixed, `f(k, m)` is monotonically increasing on `k`.
2. 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);
}
``````

• @fun4LeetCode
Could you please explain why the maximum of m will be log(n + 1)?

• @hyj143 Hi hyj143. As I said, smaller `k` corresponds to larger `m`. Since the minimum value of `k` is `2`, the corresponding value of `m` will be a maximum. Now if `k = 2`, the function `f(k, m)` will become: `f(k, m) = (k^m - 1)/(k-1) = (2^m - 1)/(2-1) = 2^m - 1`. If the equation is held true, this should be equal to the numeric value of the input string, which is `n`. Therefore we have: `2^m - 1 = n`, which leads to the maximum value of `m` as `log(n + 1)`(logarithm of `(n+1)` in base `2`).

• @fun4LeetCode

Thanks, I wasn't sure where the "plus one" come from. This is a very good math prove.

• @fun4LeetCode Nice solution. Some thoughts.

1. There is a typo in your explanation: it is `k` that is within `[(n+1)^(1/m), n^(1/(m-1)))` instead of `m`.

2. When you have the base `k`, and the digits `m`, I understand your way of calculating `f(k,m)`. But I have tried another way, which doesn't work. I just use `(long)((Math.pow(k, m)-1)/(k-1))`. Why is this wrong? numerical error?

3. Your loop already handles the case `m==2`, but why do you still need to return `String.valueOf(num -1)` at the end of the function?

4. I have once thought a solution that begins with base. For each base, we do binary search. Because we can imagine there is a 2D matrix, first dimension is base, second dimension is digits. One good property about this matrix is that along each dimension, it is always increasing. My solution is `O(nlglgn)`. So your idea is one step further and deeper than my thought.

• @dachuan.huang Hi dachuan.huang. Thanks for the feedback.

1. Nice catch. Typo corrected.
2. You are right. Take a look at this stackoverflow post
3. The final return statement is just a dummy statement required by java method.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.