BinarySearch 0843 Number of Operations to Decrement Target to Zero

Problem statement

https://binarysearch.com/problems/Number-of-Operations-to-Decrement-Target-to-Zero/

Solution

Equal to Leetcode 1658. Minimum Operations to Reduce X to Zero.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, x):
        cumsum = [0] + list(accumulate(nums))
        dic = {c:i for i,c in enumerate(cumsum)}
        goal = cumsum[-1] - x
        ans = -float("inf")

        if goal < 0: return -1

        for num in dic:
            if num + goal in dic:
                ans = max(ans, dic[num + goal] - dic[num])

        return len(nums) - ans if ans != -float("inf") else -1