imashutosh51

Minimum Operations to Reduce X to Zero

Jun 19th, 2023 (edited)
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.98 KB | None | 0 0
  1. /*
  2. Brute force is calling a function recursively and select either left or right element.
  3. 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.
  4. */
  5. class Solution:
  6.     def minOperations(self, nums: List[int], x: int) -> int:
  7.         total=sum(nums)
  8.         if total==x:
  9.             return len(nums)
  10.         if total<x:
  11.             return -1
  12.  
  13.         target=total-x
  14.         k=0
  15.         cur=0
  16.         ans=0
  17.         for i in range(len(nums)):
  18.             cur+=nums[i]
  19.             while cur>=target:
  20.                 if cur==target:
  21.                     ans=max(ans,i-k+1)
  22.                 cur-=nums[k]
  23.                 k+=1
  24.         return len(nums)-ans if ans!=0 else -1
Advertisement
Add Comment
Please, Sign In to add comment