首页 > 代码库 > LeetCode "483. Smallest Good Base" !!
LeetCode "483. Smallest Good Base" !!
A more programming-like solution, is to hack the problem from simple: we try each possble base value, and see which 111..11 fits target number - using binary search.
class Solution(object): def helper(self, num, p): l = 1; r = int(pow(num, 1.0/p) + 1) # find highest possible bit while(l < r): mid = l + (r - l) // 2 sum = 0; cur = 1 # Addup to sum by form of 1111..11 for i in xrange(0, p + 1): sum += cur cur *= mid # Good? if sum == num: return mid elif sum > num: r = mid else: l = mid + 1 return -1 def smallestGoodBase(self, N): n = int(N) # iterate each base, from longest 1s to shortest for p in xrange(2, 101): if (1 << p) < n: k = self.helper(n, p) if k != -1: return str(int(k)) return str(n-1) # 11
However, as you expect, there‘s a smarter, math solution.
https://discuss.leetcode.com/topic/76368/python-solution-with-detailed-mathematical-explanation-and-derivation
LeetCode "483. Smallest Good Base" !!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。