Description
Given an integer n represented as a string, return the smallest good base of n.
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.
Solutions
Solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution:
def smallestGoodBase(self, n: str) -> str:
def cal(k, m):
p = s = 1
for i in range(m):
p *= k
s += p
return s
num = int(n)
for m in range(63, 1, -1):
l, r = 2, num - 1
while l < r:
mid = (l + r) >> 1
if cal(mid, m) >= num:
r = mid
else:
l = mid + 1
if cal(l, m) == num:
return str(l)
return str(num - 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
30
31
32
33
34
35
36
37
38
39
40
41 | class Solution {
public String smallestGoodBase(String n) {
long num = Long.parseLong(n);
for (int len = 63; len >= 2; --len) {
long radix = getRadix(len, num);
if (radix != -1) {
return String.valueOf(radix);
}
}
return String.valueOf(num - 1);
}
private long getRadix(int len, long num) {
long l = 2, r = num - 1;
while (l < r) {
long mid = l + r >>> 1;
if (calc(mid, len) >= num)
r = mid;
else
l = mid + 1;
}
return calc(r, len) == num ? r : -1;
}
private long calc(long radix, int len) {
long p = 1;
long sum = 0;
for (int i = 0; i < len; ++i) {
if (Long.MAX_VALUE - sum < p) {
return Long.MAX_VALUE;
}
sum += p;
if (Long.MAX_VALUE / p < radix) {
p = Long.MAX_VALUE;
} else {
p *= radix;
}
}
return sum;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public:
string smallestGoodBase(string n) {
long v = stol(n);
int mx = floor(log(v) / log(2));
for (int m = mx; m > 1; --m) {
int k = pow(v, 1.0 / m);
long mul = 1, s = 1;
for (int i = 0; i < m; ++i) {
mul *= k;
s += mul;
}
if (s == v) {
return to_string(k);
}
}
return to_string(v - 1);
}
};
|