## Thursday, July 27, 2017

### LeetCode 483 - Smallest Good Base

https://leetcode.com/problems/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.
```
Example 2:
```Input: "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.
```
Example 3:
```Input: "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.
```
Note:
1. The range of n is [3, 10^18].
2. The string representing n is always valid and will not have leading zeros.
X.
http://blog.csdn.net/hanzheng992/article/details/54879692
Naive Solution是通过遍历`base`来搜索整个解空间的, 除此之外, 我们也可以通过遍历转换后`1`的位数来遍历搜索整个解空间, 这样搜索的范围会小很多.

def smallestGoodBase(self, n): """ :type n: str :rtype: str """ def getAnsofBase(length, base): """ Convert 11...11 (base `base`) to base 10 """ ans = 1 for i in xrange(length-1): ans = ans * base + 1 return ans def findLengthBase(length, n): """ Check whether there exist a base such that n in base `base` == 111...111 (length's 1s) """ start, end = 0, n/2 while start <= end: mid = (start + end) / 2 target = getAnsofBase(length, mid) if target == n: return mid elif target < n: start = mid + 1 else: end = mid - 1 return -1 num = int(n) thisLen = int(math.log(num,2)) + 1 while thisLen > 2: retVal = findLengthBase(thisLen, num) if retVal != -1: return str(retVal) thisLen -= 1 return str(num - 1)
https://discuss.leetcode.com/topic/82130/java-solution-with-hand-writing-explain
https://discuss.leetcode.com/topic/76406/java-c-binary-search-solutions-with-detailed-explanation
The java solution is submitted by lixx2100 to contest.
1. n is equal to x^(k-1) + x^(k-2) + ... + x + 1, where k is from 2 to, say, 66
2. for each k from 2 to 66, we get "x", and the minimum of all "x"s is the answer
3. To get "x", we use binary search approach with left = 2, and right = Long.MAX_VALUE
4. to compare whether n is equal to x^(k-1) + x^(k-2) + ... + x + 1, we don't need to calculate x^(k-1) + x^(k-2) + ... + x + 1 from x.
if n = x^(k-1) + x^(k-2) + ... + x + 1, then n * (x - 1) = x^k -1.
in the source code, cb is x^k -1 and wb is n * (x - 1).
``````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;
}``````
https://discuss.leetcode.com/topic/76357/java-binary-search-solution-9-ms
``````    public String smallestGoodBase(String n) {
long num = 0;
for (char c : n.toCharArray()) num = num * 10 + c - '0';

long x = 1;
for (int p = 64; p >= 1; p--) {
if ((x << p) < num) {
long k = helper(num, p);
if (k != -1) return String.valueOf(k);
}
}
return String.valueOf(num - 1);
}

private long helper(long num, int p) {
long l = 1, r = (long)(Math.pow(num, 1.0/p) + 1);
while (l < r) {
long mid = l + (r - l) / 2;
long sum = 0, cur = 1;
for (int i = 0; i <= p; i++) {
sum += cur;
cur *= mid;
}
if (sum == num) return mid;
else if (sum > num) r = mid;
else l = mid + 1;
}
return -1;
}``````
```记k的最高次幂为m，从上界 int(log(n)) 向下界 1 递减枚举m

http://blog.csdn.net/guoyuhaoaaa/article/details/54782315

http://www.gegugu.com/2017/03/14/1356.html

X. http://blog.csdn.net/hanzheng992/article/details/54879692

def smallestGoodBase(self, n): """ :type n: str :rtype: str """ def checkBase(base, n): """ Given a base, check whether it is a good base. Time complexity is O(log N) """ current = 1 while current < n: current = current * base + 1 return current == n thisNum = int(n) for i in xrange(2, thisNum): if checkBase(i, thisNum): return str(i) return str(thisNum - 1)

X.
http://blog.csdn.net/hanzheng992/article/details/54879692

base^(k-1) + base^(k-2) + … + base^1 + base^0 = N … `[1]`
base^k + base^(k-1) + … + base^2 + base^1 = N * base

base^k - base^0 = (base - 1) * N
N = (base^k - 1) / (base - 1) …. `[2]`
`[1]`, 可以得:
base ^ (k-1) < N < (base+1) ^ (k-1) … 多项式展开可证右边的不等号
base < (k-1)-th root of N < base + 1 … `[3]`

def smallestGoodBase(self, n): """ :type n: str :rtype: str """ num = int(n) thisLen = int(math.log(num,2)) + 1 while thisLen > 2: # from equation [3], we havve thisBase = int(num ** (1.0/(thisLen - 1))) # from equation [2], we have if num * (thisBase - 1) == thisBase ** thisLen - 1: return str(thisBase) thisLen -= 1 return str(num - 1)