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

• Time : O(nlon * logk)
• Space : O(n)

class Solution {
    
public:
    int minimumDeviation(vector<int>& nums) {
        priority_queue<int> pq;
        int mi = INT_MAX;
        for(int i = 0; i < nums.size(); i++) {
            nums[i] = nums[i] & 1 ? nums[i]<<1 : nums[i];
            pq.push(nums[i]);
            mi = min(mi, nums[i]);
        }
        int res = INT_MAX;
        while(!(pq.top() & 1)) {
            res = min(res, pq.top() - mi);
            mi = min(mi, pq.top()/2);
            pq.push(pq.top()/2);
            pq.pop();
        }
        
        return min(res, pq.top() - mi);
    }
};