https://leetcode.com/problems/smallest-good-base/
X.
http://www.cnblogs.com/grandyang/p/6620351.html
There is no need to search for every possible base and exponent combination. Firstly, using log2(n) we could get the maximum length of 1. Using other bases, the length is smaller than the maximum length. Secondly, using binary search instead of linear search. In such a way, the search space could be reduced to log2(n). So overall, the time complexity is log2(n)*log2*(n).
string smallestGoodBase(string n) {
long long num = stoll(n);
int maxLen = log2(num) + 1; //notice the round issue here
for(int i=maxLen; i>=1; i--)
{
long long left=2,right=num-1;
while(left <= right)
{
long long middle = (left + right) / 2;
int val = judge(middle,i,num);
if(val > 0) right = middle - 1;
else if (val < 0) left = middle + 1;
else return to_string(middle);
}
}
return to_string(num-1); //guarantee that there is at least one return of num-1. num-1 meet the requirement
}
//here judge function to decide whether base is bigger than, smaller than or equal to num
int judge(long long base,int len, long long num)
{
long long val = 0;
long long b = 1;
while(len > 0)
{
val += b;
if(val > num) return 1;
//in this case, val will also be bigger than num. This statement is used to void multiplication overflow
if ((num - val) / base < b && len > 1) return 1;
b *= base;
len--;
}
return val == num ? 0 : -1;
}
http://blog.csdn.net/hanzheng992/article/details/54879692
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
https://hk.saowen.com/a/bc893743b2b3a9afdfcb3931e0c32062a4eab5892f730463a740f6f448bd824f
首先完成字符串到數字的轉換，然後對於特定的num，當前的最長的其他進制的表示長度是進製為2時的表示長度，就是log2(num)+1（注意：10..0有t個0，那麼10..0=2^t）。那麼指數i的遍歷區間就是[1，log2(num)+1]。對於當前數的當前指數i，可能的base整數取值是num^(1/(i-1))
enumerate，但是不是结果，而是幂。方法特别巧妙，另外求幂的和还可以优化用快速幂来求。知道幂之后，根据逼近法，可以得到base：
这道题刚开始看的时候毫无头绪，感觉唯一合适的思路就是穷举了，从base为2开始一直开始往前试（因为是找最小的基，因此要从小到大的开始试），试到的那个数如果满足条件那么我们就找到了答案。这样的方法显然很笨，绝对的超时。后来看了答案，才恍然大悟，有时候换个角度去思考问题，往往能得到不错的结果。
题目中已经说了，要找到目标数aim的全‘1’表示的base。那么也就是说无论如何最后该aim的表示形式一定是全‘1’的，如果是最小的base那么也就意味着最长的‘1’串。我们可以固定一个‘1’串来找是否有合适的base可以满足，而在固定‘1’串找base的时候可以使用二分查找来节省时间。如果当前的‘1’串都不合适，那么我们就可以减少‘1’串的长度，知道找到为止，这时候‘1’串对应的base一定是最小的base。由于aim的范围是在[3, 10^18]，那么‘1’串最长无非是base为2的时候（这里的放缩其实可以适当的放大范围，并不影响整体的复杂度）。
http://www.gegugu.com/2017/03/14/1356.html
X.
http://blog.csdn.net/hanzheng992/article/details/54879692
X. Math
use mathematical equation. Time complexity: log2(n)
http://hankerzheng.com/blog/LeetCode-Smallest-Good-Base
Suppose there is one base (b) that meets the requirement (k is the number of 1, and N is the number needs to be divided):
b ^ (k-1) + b ^ (k-2) + … + b + 1 = N (1)
Based on Equation (1), we could get:
(1- b ^ k) / (1-b) = N (2) (using geometric regression equation)
(1-b ^ k) = (1-b) * N (3)
We could also get that:
b ^ (k-1) < N < (b+1) ^ (k-1)
Using binomial theorem,
(b+1)^(k-1) = b^(k-1) + C(k-1,1)*b^(k-2) + C(k-1,2)*b^(k-3) + … + 1 > b ^ (k-1) + b ^ (k-2) + … + b + 1.
So b < (k-1) th root of N < b+1, so the floor of (k-1) th root of N is equal to b.
//Solution 3: use mathematical equation
string smallestGoodBase(string n) {
long long num = stoll(n);
int maxLen = log2(num) + 1; //notice the round issue here
for (int i = maxLen; i >= 2; i--)
{
//estimate base
long long base = (long long)pow(num, 1.0 / (i - 1)); //void overflow, long long is needed here
//judge if the base meets the requirement
//using the equation (pow(base, i) - 1.0)/num == base - 1 can have overflow problem, so the judge function needs to be used
if(judge(base,i,num) == 0) return to_string(base);
}
return to_string(num - 1); //guarantee that there is at least one return of num-1. num-1 meet the requirement
}
//here judge function to decide whether base is bigger than, smaller than or equal to num
int judge(long long base, int len, long long num)
{
long long val = 0;
long long b = 1;
while (len > 0)
{
val += b;
if (val > num) return 1;
//in this case, val will also be bigger than num. This statement is used to void multiplication overflow
if ((num - val) / base < b && len > 1) return 1;
b *= base;
len--;
}
return val == num ? 0 : -1;
}
X. Brute Force
http://xinglunote.blogspot.com/2017/04/leetcode-483-smallest-good-base.html
Solution 1: Brute force traversal. Time complexity n*log(n). Time limit exceeded.
string smallestGoodBase(string n) {
long long num = stoll(n);
for(long long base=2; base<num; base++)
{
//judge if the current base can get num with all 1
long long mult = 1;
long long b = base;
while(mult<num)
{
mult += b;
b *= base;
}
if(mult == num) return to_string(base);
}
return to_string(num-1);
}
http://blog.csdn.net/hanzheng992/article/details/54879692
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:
- The range of n is [3, 10^18].
- The string representing n is always valid and will not have leading zeros.
http://www.cnblogs.com/grandyang/p/6620351.html
这道题让我们求最小的好基数，定义了一个大于等于2的基数k，如果可以把数字n转化为各位都是1的数，那么就称这个基数k是好基数。通过看题目中的三个例子，应该大致可以理解题意了吧。如果我们用k表示基数，m表示转为全1数字的位数，那么数字n就可以拆分为：
n = 1 + k + k^2 + k^3 + ... + k^(m-1)
这是一个等比数列，中学数学的内容吧，利用求和公式可以表示为 n = (k^m - 1) / (k - 1)。我们的目标是求最小的k，那么仔细观察这个式子，在n恒定的情况，k越小则m却大，那么就是说上面的等式越长越好。下面我们来分析m的取值范围，题目中给了n的范围，是[3, 10^18]。那么由于k至少为2，n至少为3，那么肯定至少有两项，则m>=2。那么m的上限该如何求？其实也不难，想要m最大，那么k就要最小，k最小是2，那么m最大只能为log2(n + 1)，数字n用二进制表示的时候可拆分出的项最多。但这道题要求变换后的数各位都是1，那么我们看题目中最后一个例子，可以发现，当k=n-1时，一定能变成11，所以实在找不到更小的情况下就返回n-1。
下面我们来确定k的范围，由于k至少为2，那么我们可以根据下面这个不等式来求k的上限：
n = 1 + k + k^2 + k^3 + ... + k^(m-1) > k^(m-1)
解出k < n^(1 / (m-1))，其实我们也可以可以通过n < k^m - 1 来求出k的准确的下限，但由于是二分查找法，下限直接使用2也没啥问题。分析到这里，那么解法应该已经跃然纸上了，我们遍历所有可能的m值，然后利用二分查找法来确定k的值，对每一个k值，我们通过联合m值算出总和sum，然后跟n来对比即可
string smallestGoodBase(string n) { long long num = stol(n); for (int i = log(num + 1) / log(2); i >= 2; --i) { long long left = 2, right = pow(num, 1.0 / (i - 1)) + 1; while (left < right) { long long mid = left + (right - left) / 2, sum = 0; for (int j = 0; j < i; ++j) { sum = sum * mid + 1; } if (sum == num) return to_string(mid); else if (sum < num) left = mid + 1; else right = mid; } } return to_string(num - 1); }http://xinglunote.blogspot.com/2017/04/leetcode-483-smallest-good-base.html
There is no need to search for every possible base and exponent combination. Firstly, using log2(n) we could get the maximum length of 1. Using other bases, the length is smaller than the maximum length. Secondly, using binary search instead of linear search. In such a way, the search space could be reduced to log2(n). So overall, the time complexity is log2(n)*log2*(n).
string smallestGoodBase(string n) {
long long num = stoll(n);
int maxLen = log2(num) + 1; //notice the round issue here
for(int i=maxLen; i>=1; i--)
{
long long left=2,right=num-1;
while(left <= right)
{
long long middle = (left + right) / 2;
int val = judge(middle,i,num);
if(val > 0) right = middle - 1;
else if (val < 0) left = middle + 1;
else return to_string(middle);
}
}
return to_string(num-1); //guarantee that there is at least one return of num-1. num-1 meet the requirement
}
//here judge function to decide whether base is bigger than, smaller than or equal to num
int judge(long long base,int len, long long num)
{
long long val = 0;
long long b = 1;
while(len > 0)
{
val += b;
if(val > num) return 1;
//in this case, val will also be bigger than num. This statement is used to void multiplication overflow
if ((num - val) / base < b && len > 1) return 1;
b *= base;
len--;
}
return val == num ? 0 : -1;
}
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)goodBase进制下, 最终得到的数是11...1, 其中有k个1. 那么k的取值范围就是[2, log(n, 2)]. 然后我们用二分查找的方式来判断是否存在这样一个整数base, 使得n通过进制转换后得到一个由k个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.
- n is equal to x^(k-1) + x^(k-2) + ... + x + 1, where k is from 2 to, say, 66
- for each k from 2 to 66, we get "x", and the minimum of all "x"s is the answer
- To get "x", we use binary search approach with left = 2, and right = Long.MAX_VALUE
- 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;
}
public String smallestGoodBase(String n) {
long num = Long.valueOf(n);
for (int m = (int) (Math.log(num + 1) / Math.log(2)); m > 2; m--) {
long l = (long) (Math.pow(num + 1, 1.0 / m));
long r = (long) (Math.pow(num, 1.0 / (m - 1)));
while (l <= r) {
long k = l + ((r - l) >> 1);
long f = 0L;
for (int i = 0; i < m; i++, f = f * k + 1)
;
if (num == f) {
return String.valueOf(k);
} else if (num < f) {
r = k - 1;
} else {
l = k + 1;
}
}
}
return String.valueOf(num - 1);
}
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;
}https://hk.saowen.com/a/bc893743b2b3a9afdfcb3931e0c32062a4eab5892f730463a740f6f448bd824f
首先完成字符串到數字的轉換，然後對於特定的num，當前的最長的其他進制的表示長度是進製為2時的表示長度，就是log2(num)+1（注意：10..0有t個0，那麼10..0=2^t）。那麼指數i的遍歷區間就是[1，log2(num)+1]。對於當前數的當前指數i，可能的base整數取值是num^(1/(i-1))
2 public String smallestGoodBase(String n) { 3 long num = Long.parseLong(n); 4 int maxIndex = (int) (Math.log(num)/Math.log(2) + 1); 5 for(int i = maxIndex; i >= 3; i--) { 6 long base = (long)Math.pow(num, 1.0 / (i - 1)), sum = 1, cur = 1; 7 for(int j = 1; j < i; j++) { 8 sum += (cur *= base); 9 } 10 if(sum == num) return String.valueOf(base); 11 // java中沒有無符號數，而且Math.pow(base, i) - 1存在精度問題，例如樣例"14919921443713777"，結果應該為"496"，但是下列語句的結果是"14919921443713776" 12 // if((long)((Math.pow(base, i) - 1) / (base - 1)) == num) return String.valueOf(base); 13 } 14 return String.valueOf(num - 1); 15 }https://segmentfault.com/a/1190000008366710
enumerate，但是不是结果，而是幂。方法特别巧妙，另外求幂的和还可以优化用快速幂来求。知道幂之后，根据逼近法，可以得到base：
k = logm(n) = (long) (pow(n, 1/m)) = (long) (log(n) / log(m))，幂的最大值是min(log2(n), 64)，当然这个是m>1的时候。注意求pow(base, m)不能直接用pow因为java里面double和long的转换过程中会丢失信息，所以要用乘来做。 public String smallestGoodBase(String n) {
long num = Long.valueOf(n);
for(int m = Math.min((int) (Math.pow(num, 0.5)), 64); m > 1; m--) {
// k = logm(num)
long k = (long) Math.pow(num, 1.0 / m);
if(isGoodBase(num, k, m)) return String.valueOf(k);
}
return String.valueOf(num - 1);
}
private boolean isGoodBase(long num, long base, int m) {
long sum = num;
long val = 1;
// calculate k^0, k^1, ..., k^m
for(int i = 0; i <= m; i++) {
sum -= val;
val *= base;
}
return sum == 0;
}这道题刚开始看的时候毫无头绪，感觉唯一合适的思路就是穷举了，从base为2开始一直开始往前试（因为是找最小的基，因此要从小到大的开始试），试到的那个数如果满足条件那么我们就找到了答案。这样的方法显然很笨，绝对的超时。后来看了答案，才恍然大悟，有时候换个角度去思考问题，往往能得到不错的结果。
题目中已经说了，要找到目标数aim的全‘1’表示的base。那么也就是说无论如何最后该aim的表示形式一定是全‘1’的，如果是最小的base那么也就意味着最长的‘1’串。我们可以固定一个‘1’串来找是否有合适的base可以满足，而在固定‘1’串找base的时候可以使用二分查找来节省时间。如果当前的‘1’串都不合适，那么我们就可以减少‘1’串的长度，知道找到为止，这时候‘1’串对应的base一定是最小的base。由于aim的范围是在[3, 10^18]，那么‘1’串最长无非是base为2的时候（这里的放缩其实可以适当的放大范围，并不影响整体的复杂度）。
http://www.gegugu.com/2017/03/14/1356.html
X.
http://blog.csdn.net/hanzheng992/article/details/54879692
假设
base是我们最终需要求的good base, k为进制转换后1的个数, 那么, 我们可以得到如下等式:
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)[2]和[3], 我们可以通过遍历位数的方法得到最终答案X. Math
use mathematical equation. Time complexity: log2(n)
http://hankerzheng.com/blog/LeetCode-Smallest-Good-Base
Suppose there is one base (b) that meets the requirement (k is the number of 1, and N is the number needs to be divided):
b ^ (k-1) + b ^ (k-2) + … + b + 1 = N (1)
Based on Equation (1), we could get:
(1- b ^ k) / (1-b) = N (2) (using geometric regression equation)
(1-b ^ k) = (1-b) * N (3)
We could also get that:
b ^ (k-1) < N < (b+1) ^ (k-1)
Using binomial theorem,
(b+1)^(k-1) = b^(k-1) + C(k-1,1)*b^(k-2) + C(k-1,2)*b^(k-3) + … + 1 > b ^ (k-1) + b ^ (k-2) + … + b + 1.
So b < (k-1) th root of N < b+1, so the floor of (k-1) th root of N is equal to b.
//Solution 3: use mathematical equation
string smallestGoodBase(string n) {
long long num = stoll(n);
int maxLen = log2(num) + 1; //notice the round issue here
for (int i = maxLen; i >= 2; i--)
{
//estimate base
long long base = (long long)pow(num, 1.0 / (i - 1)); //void overflow, long long is needed here
//judge if the base meets the requirement
//using the equation (pow(base, i) - 1.0)/num == base - 1 can have overflow problem, so the judge function needs to be used
if(judge(base,i,num) == 0) return to_string(base);
}
return to_string(num - 1); //guarantee that there is at least one return of num-1. num-1 meet the requirement
}
//here judge function to decide whether base is bigger than, smaller than or equal to num
int judge(long long base, int len, long long num)
{
long long val = 0;
long long b = 1;
while (len > 0)
{
val += b;
if (val > num) return 1;
//in this case, val will also be bigger than num. This statement is used to void multiplication overflow
if ((num - val) / base < b && len > 1) return 1;
b *= base;
len--;
}
return val == num ? 0 : -1;
}
X. Brute Force
http://xinglunote.blogspot.com/2017/04/leetcode-483-smallest-good-base.html
Solution 1: Brute force traversal. Time complexity n*log(n). Time limit exceeded.
string smallestGoodBase(string n) {
long long num = stoll(n);
for(long long base=2; base<num; base++)
{
//judge if the current base can get num with all 1
long long mult = 1;
long long b = base;
while(mult<num)
{
mult += b;
b *= base;
}
if(mult == num) return to_string(base);
}
return to_string(num-1);
}
http://blog.csdn.net/hanzheng992/article/details/54879692
根据题目意思, 很容易写出
checkBase(base,n)这个函数, 对于一个给定的baes判断该base是否为给定数n的good base, 并且这个判断函数的时间复杂度为O(log N). 搜索的空间自然为0到n - 1. 那么, 我们就能写出一个时间复杂度为O(N log N)的算法.
然而题目给定
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)n的范围为[3, 10^18], 即使是O(N log N)的方法我们也无法接受.
public String smallestGoodBase(String n) {
long num = Long.valueOf(n);
BigInteger bn = BigInteger.valueOf(num);
int max_m = (int) (Math.log(num) / Math.log(2));
for (int m = max_m; m >= 1; m--) {
BigInteger k = BigInteger.valueOf((long) Math.floor(Math.pow(num, 1.0 / m)));
BigInteger left = k.pow(m + 1).subtract(BigInteger.ONE);
BigInteger right = bn.multiply(k.subtract(BigInteger.ONE));
if (left.equals(right)) {
return String.valueOf(k);
}
}
return String.valueOf(num - 1);
}
