สมมติว่ามีจำนวนเต็ม n เรียก k ≥ 2 ว่าเป็น good base ของ n ถ้าตัวเลข n ในฐาน k ประกอบด้วยตัวเลข 1 ทั้งหมด กำหนด n เป็นสตริง ต้องคืนค่า smallest good base เป็นสตริง เช่น n = "121" → คำตอบ "3" เพราะ 121 ในฐาน 3 คือ 11111
ขั้นตอนการแก้ปัญหา
- กำหนดฟังก์ชัน getSum(x, length) คำนวณผลรวม 1 + x + x^2 + ... + x^(length-1)
- กำหนดฟังก์ชัน check(n, length) ใช้ binary search หา base x ที่ getSum(x, length) == n
- จาก main method: แปลง n เป็น int, วน length จาก 64 ลงมา 1 หา 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"
เอาต์พุต
3
