पायथन में सबसे छोटा अच्छा आधार

मान लीजिए कि हमारे पास एक पूर्णांक n है, हम k>=2 को n का एक अच्छा आधार कहते हैं, जब n आधार k के सभी अंक 1 हैं। इसलिए यदि संख्या n को स्ट्रिंग के रूप में दिया जाता है, तो हमें n का सबसे छोटा अच्छा आधार वापस करना होगा। डोरी। तो अगर संख्या 121 है, तो उत्तर 3 होगा, क्योंकि आधार 3 में 121 11111 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• गेटसम () नामक एक विधि को परिभाषित करें, इसमें x और लंबाई लगेगी
• मुख्य राशि सेट करें:=0 और अस्थायी:=1
• मैं के लिए 0 से लंबाई - 1 की सीमा में -
  • मुख्य राशि:=मुख्य योग + अस्थायी, अस्थायी:=अस्थायी * x
• मुख्य राशि लौटाएं
• चेक () नामक एक विधि को परिभाषित करें, इसमें n और लंबाई लगेगी -
• निम्न:=1, उच्च:=n
• जबकि उच्च>=निम्न −
  • मध्य :=निम्न + (उच्च - निम्न) / 2
  • मुख्य राशि:=getSum(मध्य, लंबाई)
  • अगर mainSum =n, तो बीच में वापस आएं
  • अन्यथा जब mainSum> n, तब उच्च :=मध्य – 1
  • अन्यथा निम्न :=मध्य + 1
• वापसी -1
• मुख्य विधि से निम्न कार्य करें -
• n :=दी गई संख्या
• मैं के लिए 64 से लेकर 0 तक की सीमा में
  • x :=check(n, i)
  • अगर x>=2, तो x को स्ट्रिंग के रूप में लौटाएं
• एन -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