3776. Minimum Moves to Balance Circular Array Medium

1/**
2 * [3776] Minimum Moves to Balance Circular Array
3 *
4 * You are given a circular array balance of length n, where balance[i] is the net balance of person i.
5 * In one move, a person can transfer exactly 1 unit of balance to either their left or right neighbor.
6 * Return the minimum number of moves required so that every person has a non-negative balance. If it is impossible, return -1.
7 * Note: You are guaranteed that at most 1 index has a negative balance initially.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">balance = [5,1,-4]</span>
12 * Output: <span class="example-io">4</span>
13 * Explanation:
14 * One optimal sequence of moves is:
15 * 
16 * 	Move 1 unit from i = 1 to i = 2, resulting in balance = [5, 0, -3]
17 * 	Move 1 unit from i = 0 to i = 2, resulting in balance = [4, 0, -2]
18 * 	Move 1 unit from i = 0 to i = 2, resulting in balance = [3, 0, -1]
19 * 	Move 1 unit from i = 0 to i = 2, resulting in balance = [2, 0, 0]
20 * 
21 * Thus, the minimum number of moves required is 4.
22 * </div>
23 * <strong class="example">Example 2:
24 * <div class="example-block">
25 * Input: <span class="example-io">balance = [1,2,-5,2]</span>
26 * Output: <span class="example-io">6</span>
27 * Explanation:
28 * One optimal sequence of moves is:
29 * 
30 * 	Move 1 unit from i = 1 to i = 2, resulting in balance = [1, 1, -4, 2]
31 * 	Move 1 unit from i = 1 to i = 2, resulting in balance = [1, 0, -3, 2]
32 * 	Move 1 unit from i = 3 to i = 2, resulting in balance = [1, 0, -2, 1]
33 * 	Move 1 unit from i = 3 to i = 2, resulting in balance = [1, 0, -1, 0]
34 * 	Move 1 unit from i = 0 to i = 1, resulting in balance = [0, 1, -1, 0]
35 * 	Move 1 unit from i = 1 to i = 2, resulting in balance = [0, 0, 0, 0]
36 * 
37 * Thus, the minimum number of moves required is 6.​​​
38 * </div>
39 * <strong class="example">Example 3:
40 * <div class="example-block">
41 * Input: <span class="example-io">balance = [-3,2]</span>
42 * Output: <span class="example-io">-1</span>
43 * Explanation:
44 * ​​​​​​​It is impossible to make all balances non-negative for balance = [-3, 2], so the answer is -1.
45 * </div>
46 *  
47 * Constraints:
48 * 
49 * 	1 <= n == balance.length <= 10^5
50 * 	-10^9 <= balance[i] <= 10^9
51 * 	There is at most one negative value in balance initially.
52 * 
53 */
54pub struct Solution {}
55
56// problem: https://leetcode.com/problems/minimum-moves-to-balance-circular-array/
57// discuss: https://leetcode.com/problems/minimum-moves-to-balance-circular-array/discuss/?currentPage=1&orderBy=most_votes&query=
58
59// submission codes start here
60
61impl Solution {
62    pub fn min_moves(balance: Vec<i32>) -> i64 {
63        
64    }
65}
66
67// submission codes end
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn test_3776() {
75    }
76}
77