1675. Minimize Deviation in Array #

Problem #

You are given an array nums of n positive integers.

You can perform two types of operations on any element of the array any number of times:

• If the element is even, divide it by 2.
  • 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,2].
• If the element is odd, multiply it by 2.
  • 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 [2,2,3,4].

The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some number of operations.

Example 1:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

Example 2:

Input: nums = [4,1,5,20,3]
Output: 3
Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.

Example 3:

Input: nums = [2,10,8]
Output: 3

Constraints:

• n == nums.length
• 2 <= n <= 105
• 1 <= nums[i] <= 10^9

Problem Summary #

You are given an array nums consisting of n positive integers. You can perform two types of operations on any element of the array any number of times:

• If the element is even, divide it by 2. For example, if the array is [1,2,3,4], then you can perform this operation on the last element, making it become [1,2,3,2]
• If the element is odd, multiply it by 2. For example, if the array is [1,2,3,4], then you can perform this operation on the first element, making it become [2,2,3,4] The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some operations.

Solution Approach #

• To find the minimum deviation, we need to make the maximum value smaller and the minimum value larger. To achieve this, we need to multiply and divide odd and even numbers. What is special here is that once an odd number is multiplied by 2, it becomes even. After an even number is divided by 2, it may be odd or even. So we can first multiply all odd numbers by 2, uniformly turning them into even numbers.
• In the second round, continuously divide the maximum value by 2 until the maximum value is odd and can no longer be operated on. In each loop, also divide even numbers greater than the min value by 2. Dividing by 2 here has two purposes: one is to restore the odd numbers that were multiplied by 2 in the first step, and the other is to divide the original even numbers by 2. Some people may wonder why we only make the maximum value smaller and do not make the minimum value larger. If the minimum value is odd, then it must have come from dividing a previous even number by 2, and we already calculated that even number in the previous state, so there is no need to increase it; if the minimum value is even, then in some round of division by 2, it definitely will not be operated on, meaning it will not satisfy the condition min <= nums[i]/2. In each loop, update the maximum and minimum values for that loop and record the deviation. Continue looping until the maximum value is odd, then exit the loop. Finally, output the minimum deviation.

Code #

package leetcode

func minimumDeviation(nums []int) int {
	min, max := 0, 0
	for i := range nums {
		if nums[i]%2 == 1 {
			nums[i] *= 2
		}
		if i == 0 {
			min = nums[i]
			max = nums[i]
		} else if nums[i] < min {
			min = nums[i]
		} else if max < nums[i] {
			max = nums[i]
		}
	}
	res := max - min
	for max%2 == 0 {
		tmax, tmin := 0, 0
		for i := range nums {
			if nums[i] == max || (nums[i]%2 == 0 && min <= nums[i]/2) {
				nums[i] /= 2
			}
			if i == 0 {
				tmin = nums[i]
				tmax = nums[i]
			} else if nums[i] < tmin {
				tmin = nums[i]
			} else if tmax < nums[i] {
				tmax = nums[i]
			}
		}
		if tmax-tmin < res {
			res = tmax - tmin
		}
		min, max = tmin, tmax
	}
	return res
}