Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Brute force is calling a function recursively and select either left or right element.
- 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.
- */
- class Solution:
- def minOperations(self, nums: List[int], x: int) -> int:
- total=sum(nums)
- if total==x:
- return len(nums)
- if total<x:
- return -1
- target=total-x
- k=0
- cur=0
- ans=0
- for i in range(len(nums)):
- cur+=nums[i]
- while cur>=target:
- if cur==target:
- ans=max(ans,i-k+1)
- cur-=nums[k]
- k+=1
- return len(nums)-ans if ans!=0 else -1
Advertisement
Add Comment
Please, Sign In to add comment