1675. Minimize Deviation in Array Hard

1/**
2 * [1675] Minimize Deviation in Array
3 *
4 * You are given an array nums of n positive integers.
5 * You can perform two types of operations on any element of the array any number of times:
6 * 
7 * 	If the element is even, divide it by 2.
8 * 	
9 * 		For example, if the array is [1,2,3,4], then you can do this operation on the last element, and the array will be [1,2,3,<u>2</u>].
10 * 	
11 * 	
12 * 	If the element is odd, multiply it by 2.
13 * 	
14 * 		For example, if the array is [1,2,3,4], then you can do this operation on the first element, and the array will be [<u>2</u>,2,3,4].
15 * 	
16 * 	
17 * 
18 * The deviation of the array is the maximum difference between any two elements in the array.
19 * Return the minimum deviation the array can have after performing some number of operations.
20 *  
21 * Example 1:
22 * 
23 * Input: nums = [1,2,3,4]
24 * Output: 1
25 * Explanation: You can transform the array to [1,2,3,<u>2</u>], then to [<u>2</u>,2,3,2], then the deviation will be 3 - 2 = 1.
26 * 
27 * Example 2:
28 * 
29 * Input: nums = [4,1,5,20,3]
30 * Output: 3
31 * Explanation: You can transform the array after two operations to [4,<u>2</u>,5,<u>5</u>,3], then the deviation will be 5 - 2 = 3.
32 * 
33 * Example 3:
34 * 
35 * Input: nums = [2,10,8]
36 * Output: 3
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	n == nums.length
42 * 	2 <= n <= 5 * 10^<span style="font-size: 10.8333px;">4</span>
43 * 	1 <= nums[i] <= 10^9
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/minimize-deviation-in-array/
49// discuss: https://leetcode.com/problems/minimize-deviation-in-array/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn minimum_deviation(nums: Vec<i32>) -> i32 {
55        0
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_1675() {
67    }
68}
69