Advertisement
imashutosh51

Minimum Operations to Reduce X to Zero

Jun 19th, 2023 (edited)
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.86 KB | None | 0 0
  1. /*
  2. The question here asks to minimize the operations to reduce X to zero by taking elements from either side. Let us take total sum of the array be totalSum. If X is reduced from either side, means remaining array will have sum equal to totalSum-X. As operations has to be minimized, so this question is equivalent to finding maximum size subarray having sum as totalSum-X.
  3. */
  4. class Solution:
  5.     def minOperations(self, nums: List[int], x: int) -> int:
  6.         total=sum(nums)
  7.         target=total-x
  8.         cur=0
  9.         l=0
  10.         i=0
  11.         ans=-math.inf
  12.         for i in range(len(nums)):
  13.             cur+=nums[i]
  14.             while cur>target and l<=i:
  15.                 cur-=nums[l]
  16.                 l+=1
  17.             if cur==target:
  18.                 ans=max(ans,i-l+1)
  19.        
  20.         if ans==-math.inf:
  21.             return -1
  22.         return len(nums)-ans;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement