0483. 最小好进制
题目地址（483. 最小好进制）
题目描述
1
对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。
2
3
以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。
4
5
6
7
示例 1：
8
9
输入："13"
10
输出："3"
11
解释：13 的 3 进制是 111。
12
示例 2：
13
14
输入："4681"
15
输出："8"
16
解释：4681 的 8 进制是 11111。
17
示例 3：
18
19
输入："1000000000000000000"
20
输出："999999999999999999"
21
解释：1000000000000000000 的 999999999999999999 进制是 11。
22
23
24
提示：
25
26
n的取值范围是 [3, 10^18]。
27
输入总是有效且没有前导 0。
Copied!
前置知识
- 二分法
- 进制转换
公司
- 暂无
思路
题目虽然很短，题意也不难理解。但是要想做出来还是要费一番功夫的。
题目的意思是给你一个数字 n，让你返回一个进制 k，使得 n 的 k 进制表示为 1111...111，即一个全 1 的表示，并且需要返回满足条件最小的 k。
朴素的思路是一个个尝试。不过就算想要暴力求解也要一点进制转换的知识。这个知识点是： 一个数字 n 的 k 进制表示可以按照 $a k^0 + b k^1 + c k^2 + ... + m k^{N-1}$ 的方式转化为十进制，其中 N 为 数字 n 的 k 进制位数。 比如十进制 3 的二进制是为 11，其位数就是 2。再比如十进制的 199，位数为 3。由于我们要求的是位全为 1 的数，因此系数全部为 1，也就是 a,b,c ...., m 全部为 1。
因此我们可从 k = 2 开始枚举，直到 n - 1，线性尝试是否可满足条件。
一进制只能有 0， 不可能有 1，故不考虑。 由于 n 进行最多 n 个数，上限是 n - 1，因此我们的枚举上限也是 n - 1。
核心伪代码：
1
n = int(n)
2
// 上面提到的 base 进制转十进制公式
3
func sum_with(base, N):
4
return sum(1 * base ** i for i in range(N))
5
6
for k=2 to n - 1:
7
if sum_with(k, N) == n: return k
Copied!
可问题是 N 如何求出呢？
朴素的思路仍然是线性枚举。但是我们的搜索区间如何确定呢？我们知道对于一个数 n 来说，其 2 进制表示的长度一定是大于 3 进制表示的长度的。更一般而言，如果 k1 > k2，那么对于一个数字 n 的 k1 进制表示的位数一定小于 k2 进行表示的位数。 因此我们的解空间就是 [1,x] 其中 x 为 n 的二进制表示的位数。也就是说，我们可逐一枚举 N 的值 N`。
注意到需要返回的是最小的 k 进制，结合前面说的进制越小 N 越大的知识，我们应该使用从后往前倒着遍历，这样遇到满足条件的 k 可直接返回，因此在平均意义上时间复杂度更低。
1
n = int(n)
2
// 上面提到的 base 进制转十进制公式
3
func sum_with(base, N):
4
return sum(1 * base ** i for i in range(N))
5
for N=x to 1:
6
for k=2 to n - 1:
7
if sum_with(k, N) == n: return k
Copied!
注意这里的 x 到 1 的枚举没有必要线性枚举，而是可使用二分搜索的方式进行，其依据是如果进制 k 的 N 位表示大于 n，那么 N`表示就不用看了，肯定都大，其中 N`是大于 N 的整数。
让我们来计算下上面算法的时间复杂度。外层二分枚举的时间复杂度 $O(loglogn)$，内层枚举的时间复杂度是 n，sum_with 的时间复杂度为 logn，因此总的时间复杂度为 $n\times loglogn\times logn$。
到这里为止，算法勉强可以通过了。不过仍然有优化空间。注意到 sum_with 部分其实就是一个等比数列求和，因此我们可以使用等比数列求和公式，从而将 sum_with 的时间复杂度降低到 $O(1)$。
即使如此算法的时间复杂度也是 $O(n\times loglogn)$，代入到题目是的数据范围 $[3, 10^{18}]$，也是在超时边缘。使用数学法降维打击可以获得更好的效率，感兴趣的可以研究一下。
关键点解析
- 利用等比数列求和公式可降低时间复杂度
- 从进制转换入手发现单调性，从而使用二分解决
代码
代码支持：Python3
Python3 Code:
1
class Solution:
2
def smallestGoodBase(self, n: str) -> str:
3
n = int(n)
4
# 上面提到的 base 进制转十进制公式。
5
# 使用等比数列求和公式可简化时间复杂度
6
def sum_with(base, N):
7
return (1 - base ** N) // (1 - base)
8
# return sum(1 * base ** i for i in range(N))
9
# bin(n) 会计算出 n 的二进制表示， 其会返回形如 '0b10111' 的字符串，因此需要减去 2。
10
for N in range(len(bin(n)) - 2, 0, -1):
11
l = 2
12
r = n - 1
13
while l <= r:
14
mid = (l + r) // 2
15
v = sum_with(mid, N)
16
17
if v < n:
18
l = mid + 1
19
elif v > n:
20
r = mid - 1
21
else:
22
return str(mid)
Copied!
复杂度分析
- 时间复杂度：$O(n\times loglogn)$
- 空间复杂度：$O(1)$
最近更新 1yr ago