For an integer n, we call k>=2 a good base of n, if all digits of n base k are 1.
Now given a string representing n, you should return the smallest good base of n in string format.
Example 1:
Input: "13" Output: "3" Explanation: 13 base 3 is 111.
Example 2:
Input: "4681" Output: "8" Explanation: 4681 base 8 is 11111.
Example 3:
Input: "1000000000000000000" Output: "999999999999999999" Explanation: 1000000000000000000 base 999999999999999999 is 11.
思路：刚开始Brute force想循环遍历Base，但是可能的Base太多，所以要遍历转化为该进制的长度，这个不会很大，最大log(num)/log(2)+1
接着就要找Base，可以用Binary Search
/* * Binary Search * idea is iterate on length, not base */ public class Solution { public String smallestGoodBase(String n) { long i = Long.valueOf(n); int maxLen = (int) (Math.log(i)/Math.log(2)+1); for(int l=maxLen; l>=2; l--) { int k = find(i, l); // find the base using binary search if(k != 0) return k+""; } return i-1+""; } private int find(long i, int l) { int lo=2, hi=(int) Math.pow(i, 1.0/l); while(lo <= hi) { int mid=lo+(hi-lo)/2; long sum=0, t=1; for(int j=0; j<=l; j++) { sum+=t; t*=mid; } if(sum == i) return mid; else if(sum > i) hi = mid-1; else lo = mid+1; } return 0; } }
