Python最小的良好基础

假设我们有一个整数n，当n基数k的所有数字均为1时，我们称k> = 2为n的良好底数。因此，如果数字n以字符串形式给出，则必须返回n的最小良好底数为串。因此，如果数字是121，则答案将是3，因为以3为底的121是11111。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个名为的方法getSum()，它将采用x和length

• 设置mainSum：= 0和temp：= 1

• 对于i，范围为0到长度– 1 −

• mainSum：= mainSum + temp，temp：= temp * x

• 返回mainSum

• 定义一个名为的方法check()，它将采用n和length-

• 低：= 1，高：= n

• 而高> =低-

• 中：=低+（高–低）/ 2

• mainSum：= getSum（mid，长度）

• 如果mainSum = n，则返回mid

• 否则，当mainSum> n时，则为高：=中– 1

• 否则低：=中+ 1

• 返回-1

• 从主要方法中执行以下操作-

• n：=给定的数字

• 对于我在范围64降至0

• x：=检查(n,i)

• 如果x> = 2，则返回x作为字符串

• 返回n – 1作为字符串

让我们看下面的实现以更好地理解-

示例

class Solution(object):
   def getSum(self, x, length):
      mainSum = 0
      temp = 1
      for i in range(length):
         mainSum += temp
         temp *= x
      return mainSum
   def check(self, n, length):
      low = 1
      high = n
      while high >= low:
      mid = low + (high - low) // 2
      mainSum = self.getSum(mid, length)
      if mainSum == n:
         return mid
      elif mainSum > n:
         high = mid - 1
      else:
         low = mid + 1
      return -1
   def smallestGoodBase(self, n):
      n = int(n)
      for i in range(64, 0, - 1):
         x = self.check(n, i)
      if x >= 2:
         return str(x)
      return str(n - 1)
ob = Solution()print(ob.smallestGoodBase("121"))

输入值

“121”

输出结果

3