原文链接: http://hankerzheng.com/blog/LeetCode-Smallest-Good-Base

Problem Description

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: The range of n is [3, 10^18]. The string representing n is always valid and will not have leading zeros.

中文大意: 给定一个范围在[3, 10^18]中的一个数, 找到一个进制base, 使得该数在base进制下表示的数的每一位都是1.

My Solution

Naive Solution

根据题目意思, 很容易写出checkBase(base,n)这个函数, 对于一个给定的baes判断该base是否为给定数n的good base, 并且这个判断函数的时间复杂度为O(log N). 搜索的空间自然为0到n - 1. 那么, 我们就能写出一个时间复杂度为O(N log N)的算法.

class Solution(object): def smallestGoodBase(self, n): """ :type n: str :rtype: str """ def checkBase(base, n): """ Given a base, check whether it is a good base. Time complexity is O(log N) """ current = 1 while current < n: current = current * base + 1 return current == n thisNum = int(n) for i in xrange(2, thisNum): if checkBase(i, thisNum): return str(i) return str(thisNum - 1)

然而题目给定n的范围为[3, 10^18], 即使是O(N log N)的方法我们也无法接受.

Better Solution

Naive Solution是通过遍历base来搜索整个解空间的, 除此之外, 我们也可以通过遍历转换后1的位数来遍历搜索整个解空间, 这样搜索的范围会小很多.

我们假设在goodBase进制下, 最终得到的数是11...1, 其中有k个1. 那么k的取值范围就是[2, log(n, 2)]. 然后我们用二分查找的方式来判断是否存在这样一个整数base, 使得n通过进制转换后得到一个由k个1组成的数.

该算法的时间复杂度为O(logN * logN)

import math class Solution(object): def smallestGoodBase(self, n): """ :type n: str :rtype: str """ def getAnsofBase(length, base): """ Convert 11...11 (base `base`) to base 10 """ ans = 1 for i in xrange(length-1): ans = ans * base + 1 return ans def findLengthBase(length, n): """ Check whether there exist a base such that n in base `base` == 111...111 (length's 1s) """ start, end = 0, n/2 while start <= end: mid = (start + end) / 2 target = getAnsofBase(length, mid) if target == n: return mid elif target < n: start = mid + 1 else: end = mid - 1 return -1 num = int(n) thisLen = int(math.log(num,2)) + 1 while thisLen > 2: retVal = findLengthBase(thisLen, num) if retVal != -1: return str(retVal) thisLen -= 1 return str(num - 1)

Mathmatical Solution

假设base是我们最终需要求的good base, k为进制转换后1的个数, 那么, 我们可以得到如下等式:

base^(k-1) + base^(k-2) + … + base^1 + base^0 = N … [1]

base^k + base^(k-1) + … + base^2 + base^1 = N * base

因此, 我们可以得到:

base^k - base^0 = (base - 1) * N

N = (base^k - 1) / (base - 1) …. [2]

由[1], 可以得:

base ^ (k-1) < N < (base+1) ^ (k-1) … 多项式展开可证右边的不等号

base < (k-1)-th root of N < base + 1 … [3]

根据[2]和[3], 我们可以通过遍历位数的方法得到最终答案

class Solution(object): def smallestGoodBase(self, n): """ :type n: str :rtype: str """ num = int(n) thisLen = int(math.log(num,2)) + 1 while thisLen > 2: # from equation [3], we havve thisBase = int(num ** (1.0/(thisLen - 1))) # from equation [2], we have if num * (thisBase - 1) == thisBase ** thisLen - 1: return str(thisBase) thisLen -= 1 return str(num - 1)