LC 483. 最小好进制

题目描述

这是 LeetCode 上的 483. 最小好进制 ，难度为 困难。

对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。

以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。

示例 1：

输入："13"
输出："3"
解释：13 的 3 进制是 111。

示例 2：

输入："4681"
输出："8"
解释：4681 的 8 进制是 11111。

示例 3：

输入："1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。

提示：

• n的取值范围是 [3, $10^{18}$]。
• 输入总是有效且没有前导 0。

---

基本分析

设 $(n)_{10}$ 的 $k$ 进制表示共有 $Len$ 位，那么根据「进制转换」相关知识，必然有如下等式：

$$(n)_{10} = (11...11)_{k} = k^0 + k^1 + k^2 + ... + k^{Len - 1}$$

当 $n$ 给定的情况下，$k$ 随着 $Len$ 减小而增大，由此我们可以分析出 $k$ 的上界：

• 当 $Len$ 取 $1$ 的时候：$k^0 = n$，即 $n = 1$，与题目给定的数据范围冲突，不可取；
• 当 $Len$ 取 $2$ 的时候：$k^0 + k^1 = n$，即 $k = n - 1$，为合法值。

因此 $k$ 的上界为 $n - 1$，同时我们知道长度 $Len$ 满足等式 $Len \geq 2$。

然后我们再分析一下 $Len$ 的上界。

根据 $k$ 与 $Len$ 大小变化关系，同时已知 $k \geq 2$，不难分析当 $k$ 取最小值 $2$ 的时候，$Len$ 可得最大值（同时 $n$ 的最大值为 $10^{18}$），可分析出 $Len \leq \lceil \log_2{n} \rceil$，$\log_2{10^{18}}$ 不超过 $60$。

因此可以采取枚举 $Len$ 的做法。

---

枚举 $Len$

根据分析，我们可以在 $[2, 60]$ 范围内从大到小枚举 $Len$，当取得第一位合法的 $Len$ 时，$k$ 为最小合法值。

剩下的问题在于如何在给定 $Len$ 的情况下，求得 $k$ 为多少。

前面分析到 $Len \geq 2$，令 $s = Len - 1$，再根据 二项式定理 可得：

$$n = k^0 + k^1 + k^2 + ... + k^s < C_{s}^{0} * k^0 + C_{s}^{1} * k^1 + ... + C_{s}^{s} * k^s = (k + 1)^{s}$$

同时结合 $n > k^ s$，可得 $k^s < n < (k + 1)^s$，整理后可得：

$$k < n^{\frac{1}{s}} < k + 1$$

因此，对于任意的 $s = Len - 1$ 都有唯一的解为 $n^{\frac{1}{s}}$（正整数），我们只需要验证 $n^{\frac{1}{s}}$ 是否为正整数即可。

一些细节：实现上为了方便，不处理 $k = n - 1$ 的边界问题，我们可以调整枚举下界为 $3$，当枚举不出合法 $k$ 时，直接返回 $n - 1$ 作为答案。

代码：

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);
    }
}

• 时间复杂度：$O(\log^2{n})$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.483 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。