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

ধরুন একটি পূর্ণসংখ্যা n আছে, আমরা k >= 2 কে n-এর একটি ভালো বেস বলি যদি n-এর বেস k-এ সব ডিজিট ১ হয়। যদি n স্ট্রিং হিসেবে দেওয়া থাকে, তবে n-এর সবচেয়ে ছোট ভালো বেস স্ট্রিং হিসেবে ফেরত দিতে হবে। যেমন ১২১ এর জন্য উত্তর ৩, কারণ ১২১ বেস ৩-তে ১১১১১ হয়।

সমাধানের ধাপগুলো −

• getSum() মেথড সংজ্ঞায়িত করুন যা x এবং length নেবে
• mainSum := 0, temp := 1 সেট করুন
• i = 0 থেকে length-1 পর্যন্ত − mainSum += temp, temp *= x
• mainSum রিটার্ন করুন
• check() মেথড সংজ্ঞায়িত করুন যা n এবং length নেবে
• low := 1, high := n
• while high >= low − mid = low + (high-low)//2; mainSum = getSum(mid, length); যদি mainSum == n তবে mid রিটার্ন করুন; অন্যথায় high বা low অ্যাডজাস্ট করুন
• -1 রিটার্ন করুন
• মূল মেথড থেকে − n = int(n); i = 64 থেকে 0 পর্যন্ত − x = check(n, i); যদি x >= 2 তবে str(x) রিটার্ন করুন
• str(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