https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/ from Google

Thinking process:

One idea is to exhaustive search the solution by using recursion, like for every round, we have two choices, we can either pick the current left most num or the right most num, and then call our self to figure out the minimum moves.

Since we have 2 choices every round, and the length of the number is 10^5, the time complexity will be O(2^(10^5)), which is infeasible, so we need to figure out other solution.

Based on this constraint, we need to think of a O(NlogN) or a O(N) solution. Basically, we only want to know the minimum operations we need, we don’t need to know the order. Another thing we’re sure is there must be two consecutive arrays, one starts from left most index, and the other one starts right most index.

So, we first start from picking up all numbers from left, and then we reduce the size of left array by 1. Accordingly, we need to find compensates from right. Basically this is a two pointer approach. since we only visit each position once, this is a O(N) solution.

Below is the code.

 1class Solution {
 2public:
 3    int minOperations(vector<int>& nums, int x) {
 4        int N = nums.size();
 5        int l = 0;
 6        int s = 0;
 7        int ans = -1;
 8        for (; l<N and s<x; l++) {
 9            s += nums[l];
10        }
11        if (s == x) ans = l;
12        l--;
13        int r = N - 1;
14        for (; l>=0; l--) {
15            s -= nums[l];
16            while (r > l and s < x) {
17                s += nums[r];
18                r--;
19            }
20            if (s == x) {
21                if (ans == -1) ans = (l + N - r - 1);
22                else ans = min(ans, (l + N - r - 1));
23            }
24        }
25        return ans;
26    }
27};