# 1675. Minimize Deviation in Array

#### Hard

***

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`.

  ```
  <ul>
  	<li>For example, if the array is <code>[1,2,3,4]</code>, then you can do this operation on the last element, and the array will be <code>[1,2,3,<u>2</u>].</code></li>
  </ul>
  </li>
  <li>If the element is <strong>odd</strong>, <strong>multiply</strong> it by <code>2</code>.
  <ul>
  	<li>For example, if the array is <code>[1,2,3,4]</code>, then you can do this operation on the first element, and the array will be <code>[<u>2</u>,2,3,4].</code></li>
  </ul>
  </li>
  ```

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.*

&#x20;

**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
```

&#x20;

**Constraints:**

* `n == nums.length`
* `2 <= n <= 105`
* `1 <= nums[i] <= 109`

```python
class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        heap = []
        minimum  = float("inf")
        for num in nums:
            if num % 2 == 1:
                heap.append(-num*2) # Make all odds as even
            else:
                heap.append(-num) # Keep even same
        minimum = -max(heap) # Pick Minimum from list
        # print('Minimum', minimum)
        heapq.heapify(heap)
        diff = float("inf")
        while True:
            ele = -heapq.heappop(heap) # Get max element from heap
            diff = min(diff, ele - minimum) # Get Difference b/w min and max
            # print('Element', ele)
            if ele & 1: # If Max is odd then simply return
                return diff
            ele >>= 1 # Divide by half
            minimum = min(minimum, ele) # Get new minimum
            heapq.heappush(heap, -ele) # Put half of max back to heap
        return diff
```