[LeetCode]Smallest Good Base

题目描述:

LeetCode 483. Smallest Good Base

For an integer n, we call k>=2 a good base of n, if all digits of n base k are 1.

Now given a string representing n, you should return the smallest good base of n in string format.

Example 1:

Input: "13"
Output: "3"
Explanation: 13 base 3 is 111.

Example 2:

Input: "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.

Example 3:

Input: "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.

Note:

  1. The range of n is [3, 10^18].
  2. The string representing n is always valid and will not have leading zeros.

题目大意:

给定整数n,如果n的k进制表示全部为1,则称k为n的一个“良好基数”(good base),其中k≥2

给定字符串表示的n,以字符串形式返回n的最小的“良好基数”

注意:

  1. n的取值范围是[3, 10^18]
  2. 字符串形式的n总是有效的并且不包含前导0

解题思路:

枚举法

记k的最高次幂为m,从上界 int(log(n)) 向下界 1 递减枚举m

问题转化为计算1 + k + k^2 + ... + k^m = n的正整数解

由n > k^m得: k < n ** 1/m

由n < (k + 1)^m得: k > n ** 1/m - 1,此处使用了二项式定理

因此k可能的解为:int(n ** 1/m)

最后验证1 + k + k^2 + ... + k^m 是否等于 n

Python代码:

class Solution(object):
    def smallestGoodBase(self, n):
        """
        :type n: str
        :rtype: str
        """
        n = int(n)
        for m in range(int(math.log(n, 2)), 1, -1):
            k = int(n ** (1.0 / m))
            if sum(k ** i for i in range(m + 1)) == n:
                return str(k)
        return str(n - 1)

 

本文链接:http://bookshadow.com/weblog/2017/01/22/leetcode-smallest-good-base/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. 赤壁的火神 赤壁的火神 发布于 2017年1月23日 12:53 #

    碉堡了。。。这道题我看了是一点思路都没有

  2. Jedihy Jedihy 发布于 2017年1月31日 07:00 #

    这题楼主自己做出来的?

  3. 123 123 发布于 2017年2月6日 17:35 #

    这个有原题,是google 2017 apactest round e的第二题,https://code.google.com/codejam/contest/5264487/dashboard#s=p1,楼主的方法是最优的,因为k>=2,n < 2^64,所以从转化后的进制表示的长度入手进行check,遍历,这个思路特别巧妙,想出来开m次幂的方法很棒!其实还可以对k进行二分,快速幂进行求解,但是运算结果很大,很容易溢出,不好进行判断,可以进行一些特别处理,也可以ac。楼主不要打我[可怜]

张贴您的评论