Pythonで最小のグッドベース

整数nがあるとすると、n基数kのすべての桁が1の場合、k> =2をnの基数と呼びます。したがって、数値nが文字列として指定された場合、nの最小の基数を次のように返す必要があります。ストリング。したがって、数値が121の場合、基数3の121は11111であるため、答えは3になります。

これを解決するには、次の手順に従います-

• getSum（）というメソッドを定義します。これにはxと長さが必要です
• mainSum：=0およびtemp：=1を設定します
• 0から長さ– 1 −
  の範囲のiの場合
  • mainSum：=mainSum + temp、temp：=temp * x
• mainSumを返す
• check（）というメソッドを定義します。これにはnと長さが必要です-
• 低：=1、高：=n
• 高い間>=低い-
  • 中：=低+（高–低）/ 2
  • mainSum：=getSum（mid、length）
  • mainSum =nの場合、midを返します
  • それ以外の場合、mainSum> nの場合、high：=mid – 1
  • それ以外の場合は低：=中+ 1
• 戻り値-1
• メインの方法から次のようにします-
• n：=指定された数
• 64から0までの範囲のiの場合
  • 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"))

入力

“121”

出力

3