Given an integer n represented as a string, return the smallest good base ofn.
We call k >= 2 a good base of n, if all digits of n base k are 1's.
Example 1:
**Input:** n = "13"
**Output:** "3"
**Explanation:** 13 base 3 is 111.
Example 2:
**Input:** n = "4681"
**Output:** "8"
**Explanation:** 4681 base 8 is 11111.
Example 3:
**Input:** n = "1000000000000000000"
**Output:** "999999999999999999"
**Explanation:** 1000000000000000000 base 999999999999999999 is 11.
Constraints:
n is an integer in the range [3, 1018].
n does not contain any leading zeros.
ac
class Solution {
public String smallestGoodBase(String n) {
long num = Long.parseLong(n);
int maxLen = (int) (Math.log(num + 1) / Math.log(2));
for (int len = maxLen; len >= 0; len--) {
long l = 2, r = (long) Math.pow(num, 1.0 / (len-1)) + 1;
while (l < r) {
long mid = l + (r-l)/2;
long sum = 0;
for (int i = 0; i < len; i++) sum = sum * mid + 1;
if (sum == num) return ""+mid;
else if (sum < num) l = mid + 1;
else r = mid;
}
}
return String.valueOf(num - 1);
}
}
/*
1) every bit is 1, the length range is [2, log(n+1)/log2], for each length do binary search, from max to min, because max lenght leads to smaller base; 2) base range: [2, pow(n, 1.0/(len-1)) + 1], don't understand why it's the upper, binary search to find the base; 2) every bit is 1, so with candidate base and bits, calculate if it equals n;
*/