Minimize Deviation in Array

Problem

In one operation: multiply an odd by 2, or divide an even by 2. Minimize the deviation (max - min).

Key insight: First, make all numbers even (multiply all odds by 2). Now we can only halve. Use max-heap + track min. Repeatedly halve max, update min, track best deviation.

Solutions

// C++
int minimumDeviation(vector<int>& nums) {
    priority_queue<int> maxH;
    int mn = INT_MAX;
    for (int n : nums) {
        if (n%2==1) n*=2;
        maxH.push(n);
        mn = min(mn, n);
    }
    int ans = maxH.top() - mn;
    while (maxH.top()%2==0) {
        int top = maxH.top(); maxH.pop();
        top /= 2;
        maxH.push(top);
        mn = min(mn, top);
        ans = min(ans, maxH.top()-mn);
    }
    return ans;
}

// Java
public int minimumDeviation(int[] nums) {
    PriorityQueue<Integer> maxH = new PriorityQueue<>(Collections.reverseOrder());
    int mn = Integer.MAX_VALUE;
    for (int n : nums) { if(n%2==1)n*=2; maxH.offer(n); mn=Math.min(mn,n); }
    int ans = maxH.peek() - mn;
    while (maxH.peek()%2==0) {
        int top = maxH.poll()/2; maxH.offer(top);
        mn = Math.min(mn, top);
        ans = Math.min(ans, maxH.peek()-mn);
    }
    return ans;
}

# Python
import heapq

def minimumDeviation(nums):
    heap = []
    mn = float('inf')
    for n in nums:
        if n % 2 == 1:
            n *= 2
        heapq.heappush(heap, -n)  # max-heap
        mn = min(mn, n)
    ans = -heap[0] - mn
    while heap[0] % 2 == 0:  # max is even, can halve
        top = -heapq.heappop(heap) // 2
        heapq.heappush(heap, -top)
        mn = min(mn, top)
        ans = min(ans, -heap[0] - mn)
    return ans

// JavaScript
function minimumDeviation(nums) {
    // Make all even, then use sorted array as max-heap
    nums = nums.map(n => n%2===1 ? n*2 : n);
    nums.sort((a,b) => a-b);
    let mn = nums[0], ans = nums[nums.length-1] - mn;
    while (nums[nums.length-1] % 2 === 0) {
        const top = nums.pop() / 2;
        mn = Math.min(mn, top);
        let pos = nums.findIndex(x => x >= top);
        if (pos === -1) nums.push(top); else nums.splice(pos, 0, top);
        ans = Math.min(ans, nums[nums.length-1] - mn);
    }
    return ans;
}

Complexity

Time: O(n log n * log(max_val))
Space: O(n)