<p>You are given an array <code>nums</code> of <code>n</code> positive integers.</p>

<p>You can perform two types of operations on any element of the array any number of times:</p>

<ul>
	<li>If the element is <strong>even</strong>, <strong>divide</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 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>
</ul>

<p>The <strong>deviation</strong> of the array is the <strong>maximum difference</strong> between any two elements in the array.</p>

<p>Return <em>the <strong>minimum deviation</strong> the array can have after performing some number of operations.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4]
<strong>Output:</strong> 1
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,1,5,20,3]
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,10,8]
<strong>Output:</strong> 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>2 &lt;= n &lt;= 5 * 10<sup><span style="font-size: 10.8333px;">4</span></sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        minHeap = []
        heapMax = 0

        # O(log n)
        for n in nums:
            tmp = n
            while n % 2 == 0:
                n = n // 2
            # now n should be the smllest possible number it could get to
            minHeap.append((n, max(tmp, 2 * n))) # this is so that we would add in n along with the start value if it was odd as we can go back up to that value also. This is so incase tmp was the smallest number there is no reason for us to keep on dividing
            heapMax = max(heapMax, n) # we want to largest of the whole array
        
        # by now we have the max value of the whoel array and now we want to get all teh minimum values as close to this value as possible
        # O(nlogn)
        res = float("inf")
        heapq.heapify(minHeap) # heapify the min heap so that we would sort by the first value which is the smallest case for each digit
        while len(minHeap) == len(nums):
            n, nMax = heapq.heappop(minHeap)
            res = min(res, heapMax - n) # we want the min standard deviation possible and since we start with the smallest values this would slowly get to the closest as we would slowly make the smaller values bigger

            if n < nMax: # if this condition doesn't pass then that means we are done as we have a smallest number that can't get any bigger so we are at the end
                heapq.heappush(minHeap, (n * 2, nMax)) # we want to make the smaller values bigger so if we can make n bigger so that it gets a smaller deviation then we add the new possible value to the heap and continue to check
                heapMax = max(heapMax, n * 2) # this is to update the max value in case mutlipling the value by 2 would make it now the biggest value
        return res
25700