Leetcode 483 Smallest Good Base

发表于 |

对于一个正整数n，如果将n化作k进制表示后，n的所有位全是1，我们将k叫做n的一个good base
现在给定一个字符串代表n，要求你以字符串的形式返回n的最小good base

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. n的取值范围为 [3, 10^18]
  2. 给出的代表n的字符串你可以认为是始终合法的，不存在前导0的情况

分析：

  1. 对于给定的n，假设我们将其划为k进制数，那么k的可能取值有2，n-1，在n比较大的时候显然这种方法是会超时的
  2. 那么我们需要反向思维一下，对于给定的n，将其划为长度为k的字符串，即'1'*k，那么此时的k的取值最多到60，因为 2^60 > 10^18，我们固定住k，去看能否找到一个x使得1+x+x^2+...+x^(k-1) = n，k从大往小遍历，第一个找到的x就是最小的good base
  3. 截至到上一步都很容易想到，那么关键在对于一个固定k，我们如何去计算这个x呢，根据等比数列的求和公式我们知道上式左边可化为 (x^k-1)/(x-1)，但这个式子是不可直接解的（虽然只有一个未知数），那么这时又需要反向思维一下了
  4. n = 1 + x + x^2 + … + x^(k-1),对于该式，我们可以得到
    1. n > x^(k-1)，显然
    2. n < (x+1)^(k-1)，将右边式子略作展开，显然，根据discuss中所提，这就是二项式定理
    3. 结合上面两个式子，左右同时开k-1次方，我们不妨记c为n开k-1次方的结果，则有 x < c < x+1
    4. 这里一要注意，3中式子是严格小于和严格大于的，并且c一定不可能是整数（想通这一点很关键，因为c是小数的话，我们只需要用int(c)即可得到x，但如果c是整数，那么x = int(c)-1，因为是严格小于)
  5. 根据4中步骤对于每一个k可以得到一个x值，我们接下来只需要判断3中式子是否成立了，即(x^k-1)/(x-1) == n

注意：

  1. 这道题其实是有漏洞的，因为当n>10^16时，可能是和计算机内部存储数的方式有关，有：
    1. n^1.0 = n^1 但 n^1.0 - 1 != n^1 - 1
  2. 这也是为什么代码中最后有一个return str(res)
  3. 时间复杂度是O(logn)，因为我确定的k<60，其实就是将n默认最大，然后取2的对数得出来的结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def smallestGoodBase(self, n):
        """
        :type n: str
        :rtype: str
        """
        n = int(n)
        res = n - 1
        for k in range(60,1,-1):
            c = math.fabs(1.0/(k-1))
            x = int(math.ceil(n**c-1))

            if x > 1 and  (x**k-1) // (x-1) == n:
                return str(x)
        return str(res)

O(logn) time, O(1) space
106 / 106 test cases passed.
Status: Accepted
Runtime: 42 ms,beats 65.63%