Python 中的最小好基数

pythonserver side programmingprogramming更新于 2026/1/17 20:28:17

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

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

定义一个名为 getSum() 的方法，它将采用 x 和长度
设置 mainSum := 0 和 temp := 1
对于 i 在 0 到长度范围内 – 1 −
- mainSum := mainSum + temp, temp := temp * x
返回 mainSum
定义一个名为 check() 的方法，该方法将采用 n 和长度 −
low := 1, high := n
当 high >= low −
- mid := low + (high – low) / 2
- mainSum := getSum(mid, length)
- 如果 mainSum = n，则返回 mid
- 否则当 mainSum > n 时，则 high := mid – 1
- 否则 low := mid + 1
返回 -1
从主方法执行以下操作 −
n := 给定数字
对于 i，范围从 64 到 0
- x := check(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"))