## The 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

deviationof the array is themaximum differencebetween any two elements in the array.Return the

minimum deviationthe 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] <= 109`

## Tests

```
import pytest
from .Day30_MinimizeDeviationInArray import Solution
s = Solution()
@pytest.mark.parametrize(
"nums,expected",
[
([1, 2, 3, 4], 1),
([4, 1, 5, 20, 3], 3),
([2, 10, 8], 3),
],
)
def test_minimum_deviation(nums, expected):
assert s.minimumDeviation(nums) == expected
```

## Solution

```
from typing import List
import heapq
import math
class Solution:
def minimumDeviation(self, nums: List[int]) -> int:
vals = []
minimum = math.inf
minimum_deviation = math.inf
for n in nums:
if n % 2 == 0:
vals.append(-n)
minimum = min(minimum, n)
else:
evened = n * 2
vals.append(-evened)
minimum = min(minimum, evened)
heapq.heapify(vals)
while vals:
e = -heapq.heappop(vals)
minimum_deviation = min(minimum_deviation, e - minimum)
if e % 2 != 0:
return minimum_deviation
e = e // 2
minimum = min(minimum, e)
heapq.heappush(vals, -e)
return minimum_deviation
```

## Discussion (0)