LeetCode483-最小好进制

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/smallest-good-base/

中文链接：https://leetcode-cn.com/problems/smallest-good-base/

题目详述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  1. n的取值范围是 [3, 10^18]。
  2. 输入总是有效且没有前导 0。

题目详解

  • 就是找到一个最小的进制，它的所有位为 1，恰好表示为 n。
  • 根据题意，n 的取值范围是 [3, 10^18]，这样的进制必然存在，因为存在一个 n - 1 进制它的表示为 11。
  • 这里有两个变量，一个是进制，一个是对应进制下的长度。可以固定一个变量，然后判断是否满足条件即可。进制的取值范围为 [2, n - 1]，范围太大，所以应该固定长度，判断是否存在满足条件的进制。
  • 进制越小，长度越长；进制越大，长度越短。我们可以从大到小枚举长度，判断是否存在满足条件的进制，这一步可以运用二分查找。
  • 枚举长度的时间复杂度为 O(logn)，二分查找的时间复杂度为 O(logn)，辅助计算的时间复杂度为 O(logn)，总的时间复杂度为 O(logn ^ 3)。
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
public class LeetCode_00483 {

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