3096. Minimum Levels to Gain More Points Medium

1/**
2 * [3096] Minimum Levels to Gain More Points
3 *
4 * You are given a binary array possible of length n.
5 * Alice and Bob are playing a game that consists of n levels. Some of the levels in the game are impossible to clear while others can always be cleared. In particular, if possible[i] == 0, then the i^th level is impossible to clear for both the players. A player gains 1 point on clearing a level and loses 1 point if the player fails to clear it.
6 * At the start of the game, Alice will play some levels in the given order starting from the 0^th level, after which Bob will play for the rest of the levels.
7 * Alice wants to know the minimum number of levels she should play to gain more points than Bob, if both players play optimally to maximize their points.
8 * Return the minimum number of levels Alice should play to gain more points. If this is not possible, return -1.
9 * Note that each player must play at least 1 level.
10 *  
11 * <strong class="example">Example 1:
12 * <div class="example-block">
13 * Input: <span class="example-io">possible = [1,0,1,0]</span>
14 * Output: <span class="example-io">1</span>
15 * Explanation:
16 * Let's look at all the levels that Alice can play up to:
17 * 
18 * 	If Alice plays only level 0 and Bob plays the rest of the levels, Alice has 1 point, while Bob has -1 + 1 - 1 = -1 point.
19 * 	If Alice plays till level 1 and Bob plays the rest of the levels, Alice has 1 - 1 = 0 points, while Bob has 1 - 1 = 0 points.
20 * 	If Alice plays till level 2 and Bob plays the rest of the levels, Alice has 1 - 1 + 1 = 1 point, while Bob has -1 point.
21 * 
22 * Alice must play a minimum of 1 level to gain more points.
23 * </div>
24 * <strong class="example">Example 2:
25 * <div class="example-block">
26 * Input: <span class="example-io">possible = [1,1,1,1,1]</span>
27 * Output: <span class="example-io">3</span>
28 * Explanation:
29 * Let's look at all the levels that Alice can play up to:
30 * 
31 * 	If Alice plays only level 0 and Bob plays the rest of the levels, Alice has 1 point, while Bob has 4 points.
32 * 	If Alice plays till level 1 and Bob plays the rest of the levels, Alice has 2 points, while Bob has 3 points.
33 * 	If Alice plays till level 2 and Bob plays the rest of the levels, Alice has 3 points, while Bob has 2 points.
34 * 	If Alice plays till level 3 and Bob plays the rest of the levels, Alice has 4 points, while Bob has 1 point.
35 * 
36 * Alice must play a minimum of 3 levels to gain more points.
37 * </div>
38 * <strong class="example">Example 3:
39 * <div class="example-block">
40 * Input: <span class="example-io">possible = [0,0]</span>
41 * Output: <span class="example-io">-1</span>
42 * Explanation:
43 * The only possible way is for both players to play 1 level each. Alice plays level 0 and loses 1 point. Bob plays level 1 and loses 1 point. As both players have equal points, Alice can't gain more points than Bob.
44 * </div>
45 *  
46 * Constraints:
47 * 
48 * 	2 <= n == possible.length <= 10^5
49 * 	possible[i] is either 0 or 1.
50 * 
51 */
52pub struct Solution {}
53
54// problem: https://leetcode.com/problems/minimum-levels-to-gain-more-points/
55// discuss: https://leetcode.com/problems/minimum-levels-to-gain-more-points/discuss/?currentPage=1&orderBy=most_votes&query=
56
57// submission codes start here
58
59impl Solution {
60    pub fn minimum_levels(possible: Vec<i32>) -> i32 {
61        0
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_3096() {
73    }
74}
75