We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Reduce X to Zero

Number: 1776

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Adobe, Apple

Problem Description

Given an integer array and a target number x, you can remove elements from either the start or the end of the array. The goal is to perform the minimum number of removals so that the sum of the removed elements equals exactly x. If it is not possible, return -1.

Key Insights

  • Instead of directly simulating removals from both ends, notice that removing some prefix and suffix is equivalent to keeping a contiguous subarray in the middle.
  • The sum of the removed elements equals x, so the sum of the remaining subarray is total sum minus x.
  • The problem reduces to finding the longest contiguous subarray with a sum equal to (total sum - x).
  • The minimal operations would then be the total number of elements minus the length of this subarray.
  • Use a sliding window approach to efficiently find the subarray in O(n) time.

Space and Time Complexity

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

Solution

The solution first calculates the total sum of the array. Then, it computes the target sum, which is the total sum minus x. The challenge now is to find the longest subarray with this target sum. A sliding window technique is used: expand the window by moving the right pointer and contract the window by moving the left pointer when the window sum exceeds the target. If the target sum is found, update the maximum subarray length accordingly. Finally, if such a subarray exists, the minimum operations required is the total number of elements minus the length of the found subarray; otherwise, return -1.

Code Solutions

# Python solution for the problem

def minOperations(nums, x):
    # Calculate total sum of the array
    total = sum(nums)
    # The target is sum of subarray we want to keep
    target = total - x
    # If target is 0, then we need all elements to be removed
    if target == 0:
        return len(nums)
    
    max_len = -1  # maximum length of subarray with sum equals target
    current_sum = 0
    left = 0
    
    # Use a sliding window approach
    for right in range(len(nums)):
        current_sum += nums[right]
        
        # If current_sum exceeds target, move left pointer to shrink the window
        while left <= right and current_sum > target:
            current_sum -= nums[left]
            left += 1
        
        # Check if the current window sums up to target
        if current_sum == target:
            max_len = max(max_len, right - left + 1)
    
    # If no subarray with target sum is found, return -1
    return len(nums) - max_len if max_len != -1 else -1

# Example usage:
print(minOperations([1,1,4,2,3], 5))  # Output: 2
← Back to All Questions