Hard

题目描述

给定一个以字符串形式表示的整数 n，返回 n 的最小好进制。

我们称 k >= 2 是 n 的好进制，如果 n 在 k 进制下的所有数位都是 1。

示例 1:

输入: n = "13"
输出: "3"
解释: 13 的 3 进制是 111。

示例 2:

输入: n = "4681"
输出: "8"
解释: 4681 的 8 进制是 11111。

示例 3:

输入: n = "1000000000000000000"
输出: "999999999999999999"
解释: 1000000000000000000 的 999999999999999999 进制是 11。

约束条件:

  • n 是范围 [3, 10^18] 内的整数
  • n 不包含任何前导零

解题思路

这道题的核心思路是理解好进制的数学性质。如果 n 在 k 进制下表示为全是 1 的数字，那么：

  • 如果有 m 位数字，则 n = k^(m-1) + k^(m-2) + … + k + 1 = (k^m - 1)/(k - 1)

解法分析：

  1. 暴力枚举法：枚举所有可能的位数 m，然后通过二分查找找到对应的进制 k。对于固定的 m，我们需要找到满足等式的 k 值。

  2. 数学优化：由于 n 的范围很大（最大到 10^18），位数 m 的范围其实有限。当 m = 2 时，k 最大为 n-1；当 m 很大时，k 接近 2。因此 m 的取值范围约为 [2, 60]。

具体算法步骤：

  1. 从最大可能的位数开始枚举（从大到小，因为位数越大对应的进制越小）
  2. 对于每个位数 m，使用二分查找寻找满足条件的进制 k
  3. 验证找到的 k 是否精确满足等式
  4. 返回找到的最小进制

特殊情况处理：

  • 当 m = 2 时，直接返回 n-1（因为 n = k + 1，所以 k = n-1）

代码实现

class Solution {
public:
    string smallestGoodBase(string n) {
        long long num = stoll(n);
        
        // 枚举位数 m，从大到小
        for (int m = 60; m >= 2; m--) {
            long long k = (long long)pow(num, 1.0 / (m - 1));
            
            // 验证 k 和 k+1
            for (long long base = max(2LL, k - 1); base <= k + 1; base++) {
                long long sum = 1, cur = 1;
                for (int i = 1; i < m; i++) {
                    cur *= base;
                    sum += cur;
                    if (sum > num) break;
                }
                if (sum == num) {
                    return to_string(base);
                }
            }
        }
        
        return to_string(num - 1);
    }
};

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        num = int(n)
        
        # 枚举位数 m，从大到小
        for m in range(60, 1, -1):
            k = int(num ** (1.0 / (m - 1)))
            
            # 验证 k 和 k+1
            for base in range(max(2, k - 1), k + 2):
                total = 1
                cur = 1
                for i in range(1, m):
                    cur *= base
                    total += cur
                    if total > num:
                        break
                if total == num:
                    return str(base)
        
        return str(num - 1)

public class Solution {
    public string SmallestGoodBase(string n) {
        long num = long.Parse(n);
        
        // 枚举位数 m，从大到小
        for (int m = 60; m >= 2; m--) {
            long k = (long)Math.Pow(num, 1.0 / (m - 1));
            
            // 验证 k 和 k+1
            for (long baseNum = Math.Max(2, k - 1); baseNum <= k + 1; baseNum++) {
                long sum = 1, cur = 1;
                for (int i = 1; i < m; i++) {
                    cur *= baseNum;
                    sum += cur;
                    if (sum > num) break;
                }
                if (sum == num) {
                    return baseNum.ToString();
                }
            }
        }
        
        return (num - 1).ToString();
    }
}

var smallestGoodBase = function(n) {
    const num = BigInt(n);
    const maxM = Math.floor(Math.log2(Number(num)));
    
    for (let m = maxM; m >= 2; m--) {
        const k = BigInt(Math.floor(Math.pow(Number(num), 1.0 / m)));
        
        let sum = 1n;
        let power = k;
        for (let i = 1; i < m; i++) {
            sum += power;
            power *= k;
        }
        sum += power;
        
        if (sum === num) {
            return k.toString();
        }
    }
    
    return (num - 1n).toString();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(log²n)
空间复杂度O(1)
  • 时间复杂度：外层循环最多执行 60 次（位数的上限），内层验证过程需要 O(log n) 时间
  • 空间复杂度：只使用常数额外空间