You are given an integer array nums.
Start by selecting a starting position curr such that nums[curr] == 0, and choose a movement direction of either left or right.
After that, you repeat the following process:
curr is out of the range [0, n - 1], this process ends.nums[curr] == 0, move in the current direction by incrementing curr if you are moving right, or decrementing curr if you are moving left.nums[curr] > 0:
nums[curr] by 1.A selection of the initial position curr and movement direction is considered valid if every element in nums becomes 0 by the end of the process.
Return the number of possible valid selections.
Example 1:
Input: nums = [1,0,2,0,3]
Output: 2
Explanation:
The only possible valid selections are the following:
curr = 3, and a movement direction to the left.
[1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,1,0,3] -> [1,0,1,0,3] -> [1,0,1,0,2] -> [1,0,1,0,2] -> [1,0,0,0,2] -> [1,0,0,0,2] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,0].curr = 3, and a movement direction to the right.
[1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,2,0,2] -> [1,0,2,0,2] -> [1,0,1,0,2] -> [1,0,1,0,2] -> [1,0,1,0,1] -> [1,0,1,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [0,0,0,0,0].Example 2:
Input: nums = [2,3,4,0,4,1,0]
Output: 0
Explanation:
There are no possible valid selections.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 100i where nums[i] == 0.class Solution {
public int countValidSelections(int[] nums) {
int n = nums.length, prefixSum = 0, totalSum = 0, count = 0;
for (int i : nums)
totalSum += i;
for (int i = 0; i < n; i++) {
if (nums[i] == 0) {
int postfixSum = totalSum - prefixSum;
if (postfixSum == prefixSum)
count += 2;
else if (Math.abs(postfixSum - prefixSum) == 1)
count++;
} else
prefixSum += nums[i];
}
return count;
}
}