3012. Minimize Length of Array Using Operations Medium

1/**
2 * [3012] Minimize Length of Array Using Operations
3 *
4 * You are given a 0-indexed integer array nums containing positive integers.
5 * Your task is to minimize the length of nums by performing the following operations any number of times (including zero):
6 * 
7 * 	Select two distinct indices i and j from nums, such that nums[i] > 0 and nums[j] > 0.
8 * 	Insert the result of nums[i] % nums[j] at the end of nums.
9 * 	Delete the elements at indices i and j from nums.
10 * 
11 * Return an integer denoting the minimum length of nums after performing the operation any number of times.
12 *  
13 * <strong class="example">Example 1:
14 * 
15 * Input: nums = [1,4,3,1]
16 * Output: 1
17 * Explanation: One way to minimize the length of the array is as follows:
18 * Operation 1: Select indices 2 and 1, insert nums[2] % nums[1] at the end and it becomes [1,4,3,1,3], then delete elements at indices 2 and 1.
19 * nums becomes [1,1,3].
20 * Operation 2: Select indices 1 and 2, insert nums[1] % nums[2] at the end and it becomes [1,1,3,1], then delete elements at indices 1 and 2.
21 * nums becomes [1,1].
22 * Operation 3: Select indices 1 and 0, insert nums[1] % nums[0] at the end and it becomes [1,1,0], then delete elements at indices 1 and 0.
23 * nums becomes [0].
24 * The length of nums cannot be reduced further. Hence, the answer is 1.
25 * It can be shown that 1 is the minimum achievable length. 
26 * <strong class="example">Example 2:
27 * 
28 * Input: nums = [5,5,5,10,5]
29 * Output: 2
30 * Explanation: One way to minimize the length of the array is as follows:
31 * Operation 1: Select indices 0 and 3, insert nums[0] % nums[3] at the end and it becomes [5,5,5,10,5,5], then delete elements at indices 0 and 3.
32 * nums becomes [5,5,5,5]. 
33 * Operation 2: Select indices 2 and 3, insert nums[2] % nums[3] at the end and it becomes [5,5,5,5,0], then delete elements at indices 2 and 3. 
34 * nums becomes [5,5,0]. 
35 * Operation 3: Select indices 0 and 1, insert nums[0] % nums[1] at the end and it becomes [5,5,0,0], then delete elements at indices 0 and 1.
36 * nums becomes [0,0].
37 * The length of nums cannot be reduced further. Hence, the answer is 2.
38 * It can be shown that 2 is the minimum achievable length. 
39 * <strong class="example">Example 3:
40 * 
41 * Input: nums = [2,3,4]
42 * Output: 1
43 * Explanation: One way to minimize the length of the array is as follows: 
44 * Operation 1: Select indices 1 and 2, insert nums[1] % nums[2] at the end and it becomes [2,3,4,3], then delete elements at indices 1 and 2.
45 * nums becomes [2,3].
46 * Operation 2: Select indices 1 and 0, insert nums[1] % nums[0] at the end and it becomes [2,3,1], then delete elements at indices 1 and 0.
47 * nums becomes [1].
48 * The length of nums cannot be reduced further. Hence, the answer is 1.
49 * It can be shown that 1 is the minimum achievable length.
50 *  
51 * Constraints:
52 * 
53 * 	1 <= nums.length <= 10^5
54 * 	1 <= nums[i] <= 10^9
55 * 
56 */
57pub struct Solution {}
58
59// problem: https://leetcode.com/problems/minimize-length-of-array-using-operations/
60// discuss: https://leetcode.com/problems/minimize-length-of-array-using-operations/discuss/?currentPage=1&orderBy=most_votes&query=
61
62// submission codes start here
63
64impl Solution {
65    pub fn minimum_array_length(nums: Vec<i32>) -> i32 {
66        0
67    }
68}
69
70// submission codes end
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn test_3012() {
78    }
79}
80