## DEV Community

Abhishek Chaudhary

Posted on

# Minimum Operations to Reduce X to Zero

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

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`

SOLUTION:

``````class Solution:
def lenOfLongestSubarrayWithSum(self, arr, n, k):
prevsums = {}
total = 0
maxLen = 0
for i in range(n):
total += arr[i]
if (total == k):
maxLen = i + 1
elif (total - k) in prevsums:
maxLen = max(maxLen, i - prevsums[total - k])
if total not in prevsums:
prevsums[total] = i
return maxLen

def minOperations(self, nums: List[int], x: int) -> int:
n = len(nums)
total = sum(nums)
if total == x:
return n
k = self.lenOfLongestSubarrayWithSum(nums, n, total - x)
if k == 0:
return -1
return n - k
``````