99. Minimum Operations to Reduce X to Zero

Given an integer array nums and integer x, in one operation you can remove the leftmost or rightmost element and subtract its value from x. Return the minimum number of operations to reduce x to exactly 0, or -1 if impossible.

Input: Integer array nums and integer x.

Output: Minimum operations or -1.

Examples

Input: [1,1,4,2,3],5
Output: 2
Explanation: Remove 3 from right, 2 from right: 5-3-2=0. 2 operations.

Input: [5,6,7,8,9],4
Output: -1
Explanation: Cannot reach 0.

Input: [3,2,20,1,1,3],10
Output: 5
Explanation: Remove 1,1,20,2,3 doesn't work... Remove 3,1,1,3,2 from ends = 10 in 5 ops.

Constraints

• 1<=nums.length<=10^5
• 1<=nums[i]<=10^4
• 1<=x<=10^9

Asked by