最小好进制
难度:
标签:
题目描述
以字符串的形式给出 n , 以字符串的形式返回 n 的最小 好进制 。
如果 n 的 k(k>=2) 进制数的所有数位全为1，则称 k(k>=2) 是 n 的一个 好进制 。
示例 1：
输入：n = "13" 输出："3" 解释：13 的 3 进制是 111。
示例 2：
输入：n = "4681" 输出："8" 解释：4681 的 8 进制是 11111。
示例 3：
输入：n = "1000000000000000000" 输出："999999999999999999" 解释：1000000000000000000 的 999999999999999999 进制是 11。
提示：
n的取值范围是[3, 1018]n没有前导 0
代码结果
运行时间: 32 ms, 内存: 16.0 MB
/*
* 思路：
* 通过二分查找确定 k，使得 n 能被表示成 k 进制的全1形式。
* 使用 Java Stream 进行流式操作，利用 IntStream 进行范围遍历。
*/
import java.util.stream.IntStream;
public class Solution {
public String smallestGoodBase(String n) {
long num = Long.parseLong(n);
return IntStream.rangeClosed(2, (int)(Math.log(num + 1) / Math.log(2)))
.mapToObj(m -> new Object() {
long k = (long)(Math.pow(num, 1.0 / m));
long sum = IntStream.rangeClosed(0, m).mapToLong(i -> (long) Math.pow(k, i)).sum();
})
.filter(obj -> obj.sum == num)
.map(obj -> String.valueOf(obj.k))
.findFirst()
.orElse(String.valueOf(num - 1));
}
}解释
方法:
题解利用等比数列的求和公式，结合枚举所有可能的数列长度 m (从 n 的二进制长度递减至 2) 来找到最小的好进制。对于每个 m，首先计算可能的基数 x = n的(m-1)次方根，然后验证 x 是否能够使得 n 等于从 1 到 x^(m-1) 的等比数列和。如果满足条件，即为所求的最小好进制。
时间复杂度:
O(log(n))
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中，你是如何估算等比数列求和公式 `n = (x^m - 1) / (x - 1)` 中的基数 `x` 和长度 `m` 的关系？
▷🦆
为什么题解选择从 `n` 的二进制长度递减至 2 遍历数列长度 `m`？这样的递减遍历对算法的效率有何影响？
▷🦆
题解中提到对每个可能的长度 `m`，计算 `x` 为 `n` 的 `(m-1)` 次方根，这种计算方法在哪些情况下可能不准确，如何改进？
▷