มีรายการ target เริ่มจาก X เป็็น 1 ทุกตัว ทำซ้ำ: เลือก i ตั้ง X[i] = sum(X) ตรวจสอบว่าได้ target หรือไม่
เช่น target=[5,9,3] ให้ True: [1,1,1]→[1,1,3]→[5,1,3]→[5,9,3]
ขั้นตอนการแก้ปัญหา
- ถ้าความยาว 1: ต้องเป็น [1]
- Max-heap (เก็บค่าลบ) ของ target
- วน: pop ค่ามากสุด x, d = sum-x
x2 = x % d (ถ้า d>1 ไม่อย่างนั้น 1)- อัปเดต sum, push x2 กลับ
- จนกว่า x==x2 (ไม่เปลี่ยน)
- ถ้าทุกค่าเป็น 1 คืน True
ตัวอย่างโค้ด
class Solution:
def solve(self, nums):
if len(nums) == 1: return nums == [1]
from heapq import heapify, heappop, heappush
q = [-x for x in nums]
heapify(q)
s = sum(nums)
ok = True
while ok:
x = -heappop(q)
d = s - x
x2 = x % d if d > 1 else 1
s += x2 - x
ok = x != x2
x = x2
heappush(q, -x)
return all(x == -1 for x in q)
ob = Solution()
target = [5,9,3]
print(ob.solve(target))
อินพุต
[5, 9, 3]
เอาต์พุต
True
