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
Related Topics:
Two Pointers, Binary Search, Greedy
Similar Questions:
// OJ: https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minOperations(vector<int>& A, int x) {
int N = A.size(), i = 0, j = N - 1, left = 0, right = 0, ans = N + 1;
for (; i < N && left < x; ++i) left += A[i];
if (left < x) return -1;
if (left == x) ans = i;
while (i > 0) {
left -= A[--i];
while (left + right < x) right += A[j--];
if (left + right == x) ans = min(ans, i + N - 1 - j);
}
return ans == N + 1 ? -1 : ans;
}
};