สมมติว่าเรามีจำนวนเต็ม n เราเรียก k>=2 เป็นฐานดีของ n เมื่อเลขทั้งหมดของ n ฐาน k เป็น 1 ดังนั้นหากตัวเลข n เป็นสตริง เราจะต้องคืนค่าฐานดีที่น้อยที่สุดของ n เป็น สตริง ดังนั้นหากตัวเลขคือ 121 คำตอบจะเป็น 3 เนื่องจาก 121 ในฐาน 3 คือ 11111
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดวิธีการที่เรียกว่า getSum() ซึ่งจะใช้ x และความยาว
- ตั้งค่า mainSum :=0 และ temp :=1
- สำหรับ i ในช่วง 0 ถึงความยาว – 1 −
- mainSum :=mainSum + อุณหภูมิ, อุณหภูมิ :=อุณหภูมิ * x
- คืน mainSum
- กำหนดวิธีการที่เรียกว่า check() ซึ่งจะใช้เวลา n และความยาว -
- ต่ำ :=1 สูง :=n
- ในขณะที่สูง>=ต่ำ −
- กลาง :=ต่ำ + (สูง – ต่ำ) / 2
- mainSum :=getSum(กลาง, ยาว)
- ถ้า mainSum =n ให้คืนค่า mid
- มิฉะนั้น เมื่อ mainSum> n แล้วสูง :=กลาง – 1
- มิฉะนั้น ต่ำ :=กลาง + 1
- คืน -1
- จากวิธีหลัก ให้ทำดังนี้ -
- n :=จำนวนที่กำหนด
- สำหรับ i ในช่วง 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”
ผลลัพธ์
3
