BinarySearch 0575 Resum to Target List

Problem statement

https://binarysearch.com/problems/Resum-to-Target-List/

Solution

Equal to Leetcode 1354. Construct Target Array With Multiple Sums.

Complexity

See leetcode problem complexity.

Code

class Solution:
    def solve(self, target):
        heap = []
        for num in target: heappush(heap, -num)
        s = sum(target)
        while True:
            elem = -heappop(heap)
            if elem == 1: return True
            if s == elem: return False
            cand = (elem - 1) % (s - elem) + 1
            if cand == elem: return False
            s = s - elem + cand
            heappush(heap, -cand)