519. Minimum Operations to Reduce X to Zero

Given an array and an integer x, in each operation you remove either the leftmost or the rightmost element, subtracting its value from x. Return the minimum number of operations to reduce x to exactly zero, or -1 if impossible. Equivalently, find the longest middle subarray summing to (total - x). Input: '[arr], x'.

Input: '[arr], x'.

Output: Integer — the minimum operations, or -1.

Examples

Input: [1,1,4,2,3], 5
Output: 2
Explanation: Remove 3 and 2 from the right.

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 from both ends.

Constraints

• 1<=n<=10^5
• 1<=value<=10^4
• 1<=x<=10^9

Asked by