Advertisement
imashutosh51

Minimum Operations to Reduce X to Zero

Jun 19th, 2023
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 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. public:
  6.     int minOperations(vector<int>& nums, int x) {
  7.         int sum=0;
  8.         for(int itr:nums){
  9.             sum+=itr;
  10.         }
  11.         if(sum==x) return nums.size();
  12.         sum-=x;
  13.         int ans=-1,l=0;
  14.         int cur=0;
  15.         for(int i=0;i<nums.size();i++){
  16.             cur+=nums[i];
  17.             if(i==2) cout<<cur<<endl;
  18.             while(l<i && cur>sum){
  19.                 cur-=nums[l];
  20.                 l++;
  21.             }
  22.             if(cur==sum) ans=max(ans,i-l+1);
  23.         }
  24.         if(ans==-1) return -1;
  25.         else return nums.size()-ans;
  26.     }
  27. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement