GuilinDev
Lc0483
05 August 2008
483 Smallest Good Base
对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。
以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。
时间复杂度：O(log2n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public String smallestGoodBase(String n) {
long m = Long.parseLong(n);
int max = (int)(Math.log(m) / Math.log(2) + 1);
for (int len = max; len >= 3; len--) {
long k = (long)Math.pow(m, 1.0 / (len - 1));
long res = 0;
for (int i = 0; i < len; i++) res = res * k + 1;
if (res == m) return String.valueOf(k);
}
return String.valueOf(m - 1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
/* 二分 */
public String smallestGoodBase(String n) {
long num = Long.parseLong(n);
// 枚举 k进制 中 1 的个数，最多为 二进制 时的位数
for (int i = (int) (Math.log(num) / Math.log(2) + 1); i > 2; --i) {
// k^0 + k^1 + …… + k^(i-1) = n -- 通过二分法计算 k
long left = 2, right = num - 1;
while (left <= right) {
long mid = (left + right) / 2;
long s = 0, MaxVal = num / mid + 1;
for (int j = 0; j < i; ++j)
if (s < MaxVal)
s = s * mid + 1;
else {
s = num + 1;
break;
}
if (s == num)
return Long.toString(mid);
else if (s > num)
right = mid - 1;
else
left = mid + 1;
}
}
return Long.toString(num - 1);
}
}