โจทย์: ให้ x, y เป็นจำนวนเต็มบวก จำนวนเต็ม n ถือว่า "Powerful" ถ้า n = x^i + y^j โดย i, j ≥ 0 หา Powerful integers ทั้งหมด ≤ bound
Input/Output
Input: x=2, y=3, bound=10 Output: [2, 3, 4, 5, 7, 9, 10] # 2=2^0+3^0, 3=2^1+3^0, 4=2^0+3^1, 5=2^1+3^1, 7=2^2+3^1, 9=2^3+3^0, 10=2^0+3^2
อัลกอริทึม
- จัดการกรณีพิเศษ x=1 และ/หรือ y=1 (ไม่มีการเติบโตแบบ Exponential)
- กรณีทั่วไป: Nested loop คำนวณ x^i + y^j จนเกิน bound
- ใช้ Set ป้องกันค่าซ้ำ
ตัวอย่างโค้ด
class Solution:
def powerfulIntegers(self, x, y, bound):
a, b = 0, 0
res = []
if x == 1 and y == 1:
if bound >= 2:
res.append(2)
elif x == 1:
while y**b + 1 <= bound:
res.append(y**b + 1)
b += 1
elif y == 1:
while x**a + 1 <= bound:
res.append(x**a + 1)
a += 1
else:
while x**a + 1 <= bound:
if x**a + y**b <= bound:
res.append(x**a + y**b)
b += 1
else:
a += 1
b = 0
return list(set(res))
ob = Solution()
print(ob.powerfulIntegers(2, 3, 10))
ผลลัพธ์
[2, 3, 4, 5, 7, 9, 10]
การปรับปรุง (Cleaner):
def powerfulIntegers(self, x, y, bound):
res = set()
for i in range(20): # 2^20 > 10^6, bound มัก ≤ 10^6
for j in range(20):
val = x**i + y**j
if val <= bound:
res.add(val)
else:
break
return list(res)
ใช้ Set และ Loop คงที่ 20 รอบ (เพราะ 2^20 ≈ 1M) เขียนง่ายกว่าและครอบคลุมทุกกรณี
