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

Giả sử chúng ta có một số nguyên n, 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 trong cơ số k đều là 1. 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 dưới dạng chuỗi. Ví dụ: n = 121, kết quả là 3, vì 121 trong cơ số 3 là 11111.

Các bước giải quyết:

• Định nghĩa phương thức getSum(x, length): tính tổng 1 + x + x^2 + ... + x^(length-1)
• Định nghĩa phương thức check(n, length): tìm cơ số x sao cho getSum(x, length) == n bằng tìm kiếm nhị phân
• Từ phương thức chính: duyệt length từ 64 xuống 0, gọi check(n, length), nếu tìm thấy x >= 2 thì trả về x
• Nếu không tìm thấy, trả về n - 1

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