Cơ sở tốt nhỏ nhất trong Python

Giả sử chúng ta có một số nguyên n, chúng ta gọi k> =2 là một cơ sở tốt của n, khi tất cả các chữ số của n cơ số k là 1. Vì vậy, nếu số n được cho dưới dạng chuỗi, chúng ta phải trả về cơ số tốt nhỏ nhất của n là sợi dây. Vì vậy, nếu số là 121, thì câu trả lời sẽ là 3, vì 121 trong cơ số 3 là 11111.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức được gọi là getSum (), phương thức này sẽ lấy x và độ dài
• đặt mainSum:=0 và temp:=1
• cho tôi trong phạm vi từ 0 đến độ dài - 1 -
  • mainSum:=mainSum + temp, temp:=temp * x
• trả về mainSum
• Xác định một phương thức được gọi là check (), phương thức này sẽ lấy n và chiều dài -
• thấp:=1, cao:=n
• trong khi cao> =thấp -
  • giữa:=low + (cao - thấp) / 2
  • mainSum:=getSum (giữa, chiều dài)
  • nếu mainSum =n, thì trả về giữa
  • ngược lại khi mainSum> n, thì high:=mid - 1
  • nếu không thì thấp:=mid + 1
• trả về -1
• Từ phương thức chính, hãy làm như sau -
• n:=số đã cho
• đối với tôi trong phạm vi 64 giảm xuống 0
  • x:=check (n, i)
  • nếu x> =2, thì trả về x dưới dạng chuỗi
• trả về n - 1 dưới dạng chuỗi

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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"))

Đầu vào

“121”

Đầu ra

3