পাইথনের সবচেয়ে ছোট ভাল বেস

ধরুন আমাদের একটি পূর্ণসংখ্যা n আছে, আমরা k>=2 কে n-এর একটি ভাল বেস হিসাবে বলি, যখন n বেস k-এর সমস্ত সংখ্যা 1 হয়। সুতরাং n সংখ্যাটিকে স্ট্রিং হিসাবে দেওয়া হলে, আমাদের n-এর সবচেয়ে ছোট ভাল বেস হিসাবে ফিরিয়ে দিতে হবে। স্ট্রিং সুতরাং সংখ্যাটি যদি বলা হয় 121, তাহলে উত্তর হবে 3, কারণ বেস 3-এ 121 হল 11111৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

getSum() নামে একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি x এবং দৈর্ঘ্য নেবে
সেট করুন mainSum :=0 এবং temp :=1
আমি 0 থেকে দৈর্ঘ্যের মধ্যে – 1 −
- mainSum :=mainSum + temp, temp :=temp * x
প্রধান যোগ করুন
চেক() নামে একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি n এবং দৈর্ঘ্য −
নিম্ন :=1, উচ্চ :=n
যখন উচ্চ>=কম −
- মধ্য :=নিম্ন + (উচ্চ – নিম্ন) / 2
- mainSum :=getSum(মধ্য, দৈর্ঘ্য)
- যদি mainSum =n হয়, তাহলে মাঝখানে ফিরুন
- অন্যথায় যখন mainSum> n, তারপর high :=mid – 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”

পাইথনের সবচেয়ে ছোট ভাল বেস

উদাহরণ

ইনপুট

আউটপুট