Minimum Operations to Reduce X to Zero

Master this topic with zero to advance depth.

Minimum Operations to Reduce X to Zero

Subtract values from either the left or right to reduce x exactly to 0. Return the minimum operations.

Visual Representation

nums = [1, 1, 4, 2, 3], x = 5

[1, 1] ... [3]  (Total: 5, Ops: 3)
[1] ... [2, 3]  (Total: 6, Ops: 3) X
... ... [2, 3]  (Total: 5, Ops: 2) -> BEST

Goal: Maximize middle subarray with sum (TotalSum - x)
Middle Target = 11 - 5 = 6
Max Middle = [1, 1, 4] (Len 3)
Ops = 5 - 3 = 2

Medium

Examples

Input: nums = [1,1,4,2,3], x = 5
Output: 2

Approach 1

Level I: Brute Force

Intuition

Iterate through all possible numbers of elements taken from the left end (i elements). For each i, find out how many elements from the right end are needed to reach exactly x. Track the minimum total operations.

Thought Process

Let i be the number of elements from the left (0 <= i <= nums.length).
Calculate the sum of these i elements. If sum > x, we can't take this many from left.
If sum <= x, we need to find x - sum from the right end.
Use another loop (or map) to find how many elements from right are needed.
Total operations = i + count_from_right.

⏱ O(N^2) or O(N) with Hash Map💾 O(N) for maps, or O(1) for loops.

Detailed Dry Run

Left Ops	Left Sum	Target Right	Right Ops	Total
0	0	5	2 (2, 3)	2
1 (1)	1	4	0 (None)	-
2 (1, 1)	2	3	1 (3)	3

java

import java.util.*;

public class Main {
    public static int minOperations(int[] nums, int x) {
        int n = nums.length;
        int minOps = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            int leftSum = 0;
            for (int k = 0; k < i; k++) leftSum += nums[k];
            if (leftSum > x) break;
            if (leftSum == x) {
                minOps = Math.min(minOps, i);
            } else {
                int rightSum = 0;
                for (int j = 0; j < n - i; j++) {
                    rightSum += nums[n - 1 - j];
                    if (leftSum + rightSum == x) {
                        minOps = Math.min(minOps, i + j + 1);
                        break;
                    }
                    if (leftSum + rightSum > x) break;
                }
            }
        }
        return minOps == Integer.MAX_VALUE ? -1 : minOps;
    }

    public static void main(String[] args) {
        System.out.println(minOperations(new int[]{1, 1, 4, 2, 3}, 5)); // 2
    }
}

Approach 2

Level III: Optimal (Sliding Window on Inverse Target)

Intuition

Thought Process

Finding minimum operations from the ends is the same as finding the maximum length contiguous subarray in the middle whose sum is totalSum - x. This simplifies the problem into a standard variable-size sliding window.

Patterns

Inverse Target: Target sum for window = Sum(nums) - x.
Result Mapping: Min operations from ends = TotalLength - MaxWindowLength.

⏱ O(N)💾 O(1)

Detailed Dry Run

Current Sum	Target	Max Len	Ops
1	6	-	-
2	6	-	-
6 (Found!)	6	3	5-3=2
8	6	3	-

java

public class Main {
    public static int minOperations(int[] nums, int x) {
        long totalSum = 0;
        for (int n : nums) totalSum += n;
        long target = totalSum - x;
        if (target < 0) return -1;
        if (target == 0) return nums.length;

        int left = 0, maxLen = -1;
        long currentSum = 0;
        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];
            while (currentSum > target && left <= right) {
                currentSum -= nums[left++];
            }
            if (currentSum == target) {
                maxLen = Math.max(maxLen, right - left + 1);
            }
        }
        return maxLen == -1 ? -1 : nums.length - maxLen;
    }

    public static void main(String[] args) {
        System.out.println(minOperations(new int[]{1, 1, 4, 2, 3}, 5)); // 2
    }
}

⚠️ Common Pitfalls & Tips

Edge cases: x is larger than total sum (target < 0), or x is exactly the total sum (target = 0). Use long for sums to avoid overflow if arrays are very large.

← Previous QuestionLongest Subarray of 1's After Deleting One Element

Next Question →Grumpy Bookstore Owner

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.