Minimum Operations to Reduce X to Zero - Practice Coding Problems

Minimum Operations to Reduce X to Zero - Problem

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return -1.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: Remove nums[4]=3 and nums[0]=1 (or nums[1]=1), then x becomes 5-3-1=1, then remove nums[1]=1 (or nums[0]=1). Total 2 operations to make x=0.

Example 2 — Impossible Case

$ Input: nums = [3,2,20,1,1,3], x = 10

› Output: 5

💡 Note: Remove from right: 3+1+1+3+2=10, so 5 operations needed.

Example 3 — Single Element

$ Input: nums = [5], x = 5

› Output: 1

💡 Note: Remove the only element nums[0]=5 to make x=0. One operation needed.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁴
1 ≤ x ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,1,4,2,3] and target x=5

Process

Remove elements from ends to reduce x to 0

Output

Minimum 2 operations needed

Key Takeaway

🎯 Key Insight: Transform the problem using complement thinking - find the longest middle subarray to keep instead of elements to remove from ends

Asked in

a Amazon 15 M Microsoft 12 G Google 8 f Facebook 6

The key insight is to use complement thinking: instead of finding elements to remove from ends, find the longest middle subarray to keep. The optimal sliding window approach runs in O(n) time with O(1) space by finding the longest subarray with sum = (total - x).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(n²)	O(n)	Try all possible combinations of removing elements from left and right ends
Two Pass with Hash Map	O(n)	O(n)	Calculate all left prefix sums, then use hash map to find matching right sums efficiently
Sliding Window (Complement Approach)	O(n)	O(1)	Convert to finding the longest subarray with sum = total - x (complement thinking)

Brute Force - Try All Combinations — Algorithm Steps

Calculate prefix sums for all left removals
For each left count, compute needed right sum
Check if right sum is achievable and update minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Prefix Sums

Compute all possible left removal sums

Calculate Suffix Sums

Compute all possible right removal sums

Try Combinations

For each left sum, find matching right sum that equals x

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int numsSize, int x) {
    // Calculate prefix sums (left removals)
    long long* leftSums = (long long*)calloc(numsSize + 1, sizeof(long long));
    for (int i = 0; i < numsSize; i++) {
        leftSums[i + 1] = leftSums[i] + nums[i];
    }
    
    // Calculate suffix sums (right removals)
    long long* rightSums = (long long*)calloc(numsSize + 1, sizeof(long long));
    for (int i = numsSize - 1; i >= 0; i--) {
        rightSums[numsSize - i] = rightSums[numsSize - i - 1] + nums[i];
    }
    
    int minOps = INT_MAX;
    
    // Try all combinations of left and right removals
    for (int left = 0; left <= numsSize; left++) {
        long long needed = x - leftSums[left];
        if (needed < 0) break;
        if (needed == 0) {
            if (left < minOps) minOps = left;
            continue;
        }
        
        // Find if we can get 'needed' from right
        for (int right = 1; right <= numsSize - left; right++) {
            if (rightSums[right] == needed) {
                if (left + right < minOps) minOps = left + right;
                break;
            } else if (rightSums[right] > needed) {
                break;
            }
        }
    }
    
    free(leftSums);
    free(rightSums);
    
    return minOps == INT_MAX ? -1 : minOps;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[10000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int x;
    scanf("%d", &x);
    
    int result = solution(nums, numsSize, x);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n left positions, we calculate right sum which takes O(n)

⚠ Quadratic Growth

Space Complexity

O(n)

Store prefix and suffix sums arrays

⚡ Linearithmic Space

124.5K Views

High Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler