## DEV Community is a community of 610,973 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Day 14 - Minimum Operations to Reduce X to Zero

## The 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's possible, otherwise, return -1.

Example 1:

``````Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.
``````

Example 2:

``````Input: nums = [5,6,7,8,9], x = 4
Output: -1
``````

Example 3:

``````Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.
``````

Constraints:

• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 104`
• `1 <= x <= 109`

## My Tests

``````import pytest
from .Day14_MinimumOperationsToReduceXToZero import Solution

s = Solution()

@pytest.mark.parametrize(
"nums,x,expected",
[([1, 1, 4, 2, 3], 5, 2), ([5, 6, 7, 8, 9], 4, -1), ([3, 2, 20, 1, 1, 3], 10, 5)],
)
def test_min_operations(nums, x, expected):
assert s.minOperations(nums, x) == expected

``````

## My Solution

``````from typing import List

class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
total = sum(nums)
remainder = total - x
n = len(nums)
largest_subarray_len = -1
current_sum = 0

j = 0
for i in range(n):
current_sum += nums[i]
while current_sum > remainder and j <= i:
current_sum -= nums[j]
j += 1
if current_sum == remainder:
largest_subarray_len = max(largest_subarray_len, i - j + 1)

if largest_subarray_len == -1:
return largest_subarray_len

return n - largest_subarray_len

``````

## My Commentary

There were 2 hints in the problem that I ended up using.

Think in reverse; instead of finding the minimum prefix + suffix, find the maximum subarray.

Finding the maximum subarray is standard and can be done greedily.

The Max Sub Array Problem is reasonably straightforward to solve. The bit I found tricky initially was figuring out exactly what max subarray to look for. I tried to avoid doing any pre-processing of the array but could not come up with anything good there. Finding a sub array without always going over the whole array appears to be too hard. Turns out a good solution is to think in reverse (as the hint said) and find the largest sub array what is `sum(nums) - x`. If you know the length of that sub array you can subtract its length from the length of `nums` to get the number of operations.

Even though we do sum the array at first the solution is still `O(n)` so not too bad.