483. Smallest Good Base

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.
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
      
      

Example 2:

登录后复制

      
      

       
       Input: "4681"
       
       
Output: "8"
       
       
Explanation: 4681 base 8 is 11111.
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
      
      

Example 3:

登录后复制

      
      

       
       Input: "1000000000000000000"
       
       
Output: "999999999999999999"
       
       
Explanation: 1000000000000000000 base 999999999999999999 is 11.
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
      
      

Note:
The range of n is [3, 10^18].
The string representing n is always valid and will not have leading zeros.

思路：
首先完成字符串到数字的转换，然后对于特定的num，当前的最长的其他进制的表示长度是进制为2时的表示长度，就是log2(num)+1（注意：10..0有t个0，那么10..0=2^t）。那么指数i的遍历区间就是[1，log2(num)+1]。对于当前数的当前指数i，可能的base整数取值是num^(1/(i-1))。

登录后复制

      
      

       
       class Solution {
       
       
    public String smallestGoodBase(String n) {
       
       
        long num = Long.parseLong(n);
       
       
        int maxIndex = (int) (Math.log(num)/Math.log(2) + 1);
       
       
        for(int i = maxIndex; i >= 3; i--) {
       
       
            long base = (long)Math.pow(num, 1.0 / (i - 1)), sum = 1, cur = 1;
       
       
            for(int j = 1; j < i; j++) {
       
       
                sum += (cur *= base);
       
       
            }
       
       
            if(sum == num) return String.valueOf(base);
       
       
        }
       
       
        return String.valueOf(num - 1);
       
       
    }
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.