## 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 thismodifiesthe array for future operations.Return the

minimum numberof 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
```

## Analysis

## 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.

## Top comments (0)