You are given a circular array balance of length n, where balance[i] is the net balance of person i.
In one move, a person can transfer exactly 1 unit of balance to either their left or right neighbor.
Return the minimum number of moves required so that every person has a non-negative balance. If it is impossible, return -1.
Example 1:
Input: balance = [-1,2,-1]
Output: 2
Explanation:
One optimal sequence of moves is:
i = 1 to i = 0, resulting in balance = [0, 1, -1]i = 1 to i = 2, resulting in balance = [0, 0, 0]Thus, the minimum number of moves required is 2.
Example 2:
Input: balance = [4,-1,-2]
Output: 3
Explanation:
One optimal sequence of moves is:
i = 0 to i = 1, resulting in balance = [3, 0, -2]i = 0 to i = 2, resulting in balance = [2, 0, -1]i = 0 to i = 2, resulting in balance = [1, 0, 0]Thus, the minimum number of moves required is 3.
Example 3:
Input: balance = [-3,-3,5]
Output: -1
Explanation:
It is impossible to make all balances non-negative for balance = [-3, -3, 5], so the answer is -1.
Constraints:
1 <= n == balance.length <= 1000-105 <= balance[i] <= 105No sample inputs for this problem yet. The examples in the statement show the format.