483. Smallest Good Base

Link

Solution

依照等比公式: N = X^k-1/X-1, 其中X為base

N(X-1) = X^k -1 時，就表示X是一個可行的base

若X^k-1 > N(X-1) 表示X 太大, 反之則是X太小，X都不是一個可行的base

K的最大值為 log2 (10^19 ) = 60 K的最小值為 2

  public String smallestGoodBase(String n) {
        long num = Long.parseLong(n);
        long ans = 0;

        for(int k = 60; k >=2; k--){
            long min = 2;
            long max = num;
            while(max > min){
                long mid = min + (max-min)/2;
                int res = isBase(num, mid, k);
                if(res == 0){
                    ans = mid;
                    break;
                }
                else if(res > 0){
                    max = mid;
                }else{
                    min = mid+1;
                }
            }
            if(ans != 0) break;
        }
        return ""+ans;
    }
    
    public int isBase(long num, long base, int k){
        BigInteger left = (BigInteger.valueOf(base).pow(k)).subtract(BigInteger.ONE);
        BigInteger right = (BigInteger.valueOf(base).subtract(BigInteger.ONE)).multiply(BigInteger.valueOf(num));
        int cmr = left.compareTo(right);
        return cmr;
    }