Java/C# binary search solutions with detailed explanation


  • 6
    Y

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

  • 0
    Y

    @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;
    

  • 4
    S

    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 + "";
        }
    

  • 0
    Y

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

    Great observations!


  • 0
    D
    This post is deleted!

  • 0
    D

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


  • 0
    Y

    @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.


  • 0
    S

    said in Java/C# binary search solutions with detailed explanation:

    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.


  • 1
    S

    @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)


Log in to reply
 

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