2293. Min Max Game Easy

1/**
2 * [2293] Min Max Game
3 *
4 * You are given a 0-indexed integer array nums whose length is a power of 2.
5 * Apply the following algorithm on nums:
6 * <ol>
7 * Let n be the length of nums. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n / 2.
8 * For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).
9 * For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).
10 * Replace the array nums with newNums.
11 * Repeat the entire process starting from step 1.
12 * </ol>
13 * Return the last number that remains in nums after applying the algorithm.
14 *  
15 * Example 1:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2022/04/13/example1drawio-1.png" style="width: 500px; height: 240px;" />
17 * Input: nums = [1,3,5,2,4,8,2,2]
18 * Output: 1
19 * Explanation: The following arrays are the results of applying the algorithm repeatedly.
20 * First: nums = [1,5,4,2]
21 * Second: nums = [1,4]
22 * Third: nums = [1]
23 * 1 is the last remaining number, so we return 1.
24 * 
25 * Example 2:
26 * 
27 * Input: nums = [3]
28 * Output: 3
29 * Explanation: 3 is already the last remaining number, so we return 3.
30 * 
31 *  
32 * Constraints:
33 * 
34 * 1 <= nums.length <= 1024
35 * 1 <= nums[i] <= 10^9
36 * nums.length is a power of 2.
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/min-max-game/
42// discuss: https://leetcode.com/problems/min-max-game/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45use std::cmp;
46
47impl Solution {
48    pub fn min_max_game(nums: Vec<i32>) -> i32 {
49        if nums.len() == 1 {
50            return nums[0];
51        }
52
53        let mut n = vec![0; nums.len() / 2];
54        for i in 0..n.len() {
55            if i % 2 == 0 {
56                n[i] = cmp::min(nums[i * 2], nums[i * 2 + 1]);
57            } else {
58                n[i] = cmp::max(nums[i * 2], nums[i * 2 + 1]);
59            }
60        }
61        Self::min_max_game(n)
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_2293() {
73        assert_eq!(Solution::min_max_game(vec![1,3,5,2,4,8,2,2]), 1);
74    }
75}
76