# Java/C# binary search solutions with detailed explanation

• The java solution is submitted by lixx2100 to contest.

1. n is equal to x^(k-1) + x^(k-2) + ... + x + 1, where k is from 2 to, say, 66
2. for each k from 2 to 66, we get "x", and the minimum of all "x"s is the answer
3. To get "x", we use binary search approach with left = 2, and right = Long.MAX_VALUE
4. to compare whether n is equal to x^(k-1) + x^(k-2) + ... + x + 1, we don't need to calculate x^(k-1) + x^(k-2) + ... + x + 1 from x.
if n = x^(k-1) + x^(k-2) + ... + x + 1, then n * (x - 1) = x^k -1.
in the source code, cb is x^k -1 and wb is n * (x - 1).
import java.math.*;

public class Solution {

public String smallestGoodBase(String n) {
BigInteger N = new BigInteger(n);
long base = Long.MAX_VALUE;

for (int k = 2; k < 66; k++) {

long l = 2, r = Long.MAX_VALUE - 5;
while (l <= r) {
long mid = l + (r - l) / 2;

BigInteger cb = BigInteger.valueOf(mid).pow(k).subtract(BigInteger.ONE);
BigInteger wb = N.multiply(BigInteger.valueOf(mid).subtract(BigInteger.ONE));

int cmp = cb.compareTo(wb);
if (cmp == 0) {
base = Math.min(base, mid);
break;
} else if (cmp < 0) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}

return "" + base;
}
}

• @yuhaowang001
66 is good enough, we could also use other number, say, 100

r = Long.MAX_VALUE - 5

to avoid overflow for

long mid = l + (r - l) / 2;

• Good concept. I have couple of observations for you.

1. k can be at max 60. The least possible base is 2 and max possible number is 10^18. So k can be at max Base 2 Log(10^18) = 60 (Rounded off to the ceiling integer value).
2. In binary search, right can be utmost N - 1.
3. There is actually no need to loop over twice and thus no need to maintain min base. You can start k = 60 in outer loop and decrement it by 1 as long as it is >= 2. Hence, as soon as you find base, you can be sure that it is the minimum base possible given the fact that we have started with max k possible. Also it relies on the fact that no two bases share the same length for the given number.

Modified code looks like below: (coded in C#)

public string SmallestGoodBase(string n) {
long num = Int64.Parse(n);
long key = 0;

// length
for(int k = 60; k >= 2; k--)
{
// base
long l = 2, h = num - 1;
while(l <= h)
{
long mid = l + (h-l)/2;
BigInteger left = BigInteger.Pow(mid, k) - 1;
BigInteger right = (BigInteger)num * (mid - 1);

if(left == right)
{
key = mid;
break;
}
if(left < right)
{
l = mid + 1;
}
else
{
h = mid - 1;
}
}
if(key != 0)
{
break;
}
}
return key + "";
}

• @sameer13 said in [Java solution submitted by lixx2100 to contest (comments added)]

Great observations!

• This post is deleted!

• @sameer13 why did you apply log for 10^18. Why k can be at max base 2 log n

• @devineni
One note of the problem gives the bound of n: The range of n is [3, 10^18].

The maximum value of k would be Base 2 Log(10^18), since the minimum value of x is 2.

• if n = x^(k-1) + x^(k-2) + ... + x + 1, then n * (x - 1) = x^k -1.

Could anyone help explain why "if n = x^(k-1) + x^(k-2) + ... + x + 1, then n * (x - 1) = x^k -1.". I can understand n is a geometric sequence, but not able to understand why n * (x - 1) = x^k -1. Thanks.

• @shileiwill

We know that
1 + x + ....... + x ^ (k-1) = n

LHS in the above equation is the sum of first k numbers in this geometric series
ie 1 * ((x ^ k) - 1) / (x - 1) = n
=> ((x ^ k) - 1) = n (x - 1)

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