0483：最小好进制（★★）

力扣第 483 题

题目

以字符串的形式给出 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

分析

#1

• 显然二进制最长，最多 60 位，因此考虑遍历位数
• 对于位数 m 的 1，二分查找离 n 最近的 k 进制，判断是否等于 n 即可

1
2
3
4
5
6
7

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        n = int(n)
        for m in range(n.bit_length(),1,-1):
            k = bisect_left(range(n),n,2,key=lambda k:(pow(k,m)-1)//(k-1))
            if (pow(k,m)-1)//(k-1)==n:
                return str(k)

205 ms

#2

• 还可以用数学直接计算位数 m>2 时对应的 k
• 首先有： $$n=k^0+k^1+…+k^{m-1}>k^{m-1}$$
• 根据二项式定理又有： $$(k+1)^{m-1}=\binom{m-1}{0}k^0+\binom{m-1}{1}k^1+…+\binom{m-1}{m-1}k^{m-1} \\ >k^0+k^1+…+k^{m-1}=n $$
• 两式结合有：

$$k<n^{\frac 1 {m-1}}<k+1 \\ k=\lfloor n^{\frac 1 {m-1}} \rfloor$$

解答

1
2
3
4
5
6
7
8

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        n = int(n)
        for m in range(n.bit_length(),2,-1):
            k = int(pow(n,1/(m-1)))
            if (pow(k,m)-1)//(k-1)==n:
                return str(k)
        return str(n-1)

38 ms