Java solution with hand-writing explain


  • 14

    n is the number, x is the base.
    alt text

    public String smallestGoodBase(String nn) {
      long n = Long.parseLong(nn);
      long res = 0;
      for(int k = 60; k >= 2; k--){
        long s = 2, e = n;
        while(s < e){
            long m = s + (e - s) / 2;   
            
            BigInteger left = BigInteger.valueOf(m);
            left = left.pow(k).subtract(BigInteger.ONE);
            BigInteger right = BigInteger.valueOf(n).multiply(BigInteger.valueOf(m).subtract(BigInteger.ONE));
            int cmr = left.compareTo(right);
            if(cmr == 0){
                res =  m;
                break;
            } else if(cmr < 0){
                s = m + 1;
            } else {
                e = m;
            }
        }
        
        if(res != 0) break;
      }
      
      return "" + res;
    }

  • 1
    G

    I like your freehand writing :)


  • 0
    T

    Emulate your method:

    import java.math.*;
    
    public class Solution {
        public String smallestGoodBase(String n) {
            String res="";
            
            long nn=Long.parseLong(n);
            
            for(int k=60;k>=1;k--){
                long l=2;
                long r=nn+1;
                
                
                while(l<r){
                   long mid=l+(r-l)/2;
                   BigInteger left=BigInteger.valueOf(mid);
                   left=left.pow(k).subtract(BigInteger.ONE);
                   BigInteger right=BigInteger.valueOf(nn).multiply(BigInteger.valueOf(mid-1));
                    
                   int cmp=left.compareTo(right);
                   if(cmp==0){
                       return mid+"";
                   }else if(cmp<0){
                       l=mid+1;
                   }else{
                       r=mid;
                   }
                 }
            }
            return res;
        }
    }
    

  • 3
    S

    @Jerry said in Java solution with hand-writing explain:

    Great Solution!

    Shouldn't the inequalities be the other way around?
    i.e. n(x-1) > (x^k - 1) implies x is too small
    and n(x-1) < (x^k - 1) implies x is too large


Log in to reply
 

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