Minimum Operations to Reduce X to Zero [Medium] — Complement Window

Problem Statement

Remove elements from either end of nums (each removal = 1 operation) until their sum equals x. Return minimum operations, or -1 if impossible.

Input: nums=[1,1,4,2,3], x=5 → Output: 2 (remove [2,3] or [1,4])

Intuition

Instead of taking elements from ends, find the longest middle subarray with sum = total - x. Complement: ops = n - longest_subarray_length.

Solutions

C++

int minOperations(vector<int>& nums, int x) {
    int total=accumulate(nums.begin(),nums.end(),0), target=total-x;
    if(target<0) return -1;
    if(target==0) return nums.size();
    int left=0, sum=0, ans=-1;
    for(int r=0;r<nums.size();r++){
        sum+=nums[r];
        while(sum>target&&left<=r) sum-=nums[left++];
        if(sum==target) ans=max(ans,r-left+1);
    }
    return ans==-1?-1:(int)nums.size()-ans;
}

Java

public int minOperations(int[] nums, int x) {
    int total=0; for(int n:nums)total+=n;
    int target=total-x; if(target<0)return -1; if(target==0)return nums.length;
    int left=0,sum=0,ans=-1;
    for(int r=0;r<nums.length;r++){
        sum+=nums[r];
        while(sum>target)sum-=nums[left++];
        if(sum==target)ans=Math.max(ans,r-left+1);
    }
    return ans==-1?-1:nums.length-ans;
}

Python

def minOperations(nums: list[int], x: int) -> int:
    target = sum(nums) - x
    if target < 0: return -1
    if target == 0: return len(nums)
    left = s = 0; best = -1
    for right, val in enumerate(nums):
        s += val
        while s > target: s -= nums[left]; left += 1
        if s == target: best = max(best, right - left + 1)
    return -1 if best == -1 else len(nums) - best

Complexity

Time: O(n), Space: O(1)