{x}
blog image

Minimize Deviation in Array

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 <= 5 * 104
  • 1 <= nums[i] <= 109

Solution Explanation: Minimize Deviation in Array

This problem asks us to find the minimum deviation achievable in an array by repeatedly dividing even numbers by 2 or multiplying odd numbers by 2. The deviation is the difference between the maximum and minimum elements.

Core Idea: A greedy approach works best here. The key insight is that repeatedly dividing even numbers by 2 will eventually lead to a smaller deviation. We focus on reducing the maximum element while trying to keep the minimum element relatively large.

Algorithm:

  1. Initialization:

    • Create a max-heap (priority queue) to store the elements.
    • Iterate through the input array nums:
      • If an element is odd, multiply it by 2.
      • Add the (possibly modified) element to the max-heap.
      • Keep track of the minimum element (mi) encountered so far.

  2. Iteration:

    • While the maximum element (top of the heap) is even:
      • Remove the maximum element (x) from the heap.
      • Divide x by 2.
      • Add the new value (x / 2) back to the heap.
      • Update mi if the new value is smaller.
      • Calculate the current deviation (ans) as the difference between the maximum and minimum elements. Update ans to the minimum deviation seen so far.

  3. Return: Return the minimum deviation (ans).

Time Complexity Analysis:

  • The initial iteration to build the heap takes O(n log n) time.
  • In the worst case, each element might be divided by 2 up to log(max(nums)) times. Each heappop and heappush operation takes O(log n) time. Therefore, the overall time complexity is O(n log n + n log(max(nums)) log n), which simplifies to O(n log n log(max(nums))). If we consider the maximum value of the elements to be bounded by a constant, then the complexity is dominated by O(n log n).

Space Complexity: O(n) to store the heap.

Code Examples:

The code examples provided (Python, Java, C++, Go) all implement this greedy algorithm using a max-heap (priority queue). The differences lie primarily in syntax and the specific heap implementation used by each language. Note the use of bitwise operations (<<= 1, >>= 1, & 1) for efficiency in multiplying/dividing by 2. The Go code uses a custom heap implementation for better clarity and control, which is a common practice when working with heaps in Go. The other solutions leverage built-in priority queue functionality in their respective languages.