Minimize Deviation in Array

hard heap greedy

Problem

You may any number of times: halve an even number (×0.5, floor) or double an odd number. Minimize max−min after operations.

Inputnums = [1,2,3,4]

Output1

Double 1→2 and 3→6 → [2,2,6,4]; then halve 6→3, 4→2 → [2,2,3,2]; spread = 1.

nums

import heapq
def minimum_deviation(nums):
    heap = []
    cur_min = float('inf')
    for x in nums:
        if x % 2 == 1: x *= 2
        heap.append(-x)
        cur_min = min(cur_min, x)
    heapq.heapify(heap)
    best = -heap[0] - cur_min
    while -heap[0] % 2 == 0:
        top = -heapq.heappop(heap) // 2
        cur_min = min(cur_min, top)
        heapq.heappush(heap, -top)
        best = min(best, -heap[0] - cur_min)
    return best

// Max-heap via negated values; uses a tiny inline heap.
function minimumDeviation(nums) {
  const heap = [];
  let lo = Infinity;
  function push(v) { heap.push(v); let i = heap.length - 1; while (i && heap[(i-1)>>1] < heap[i]) { [heap[i], heap[(i-1)>>1]] = [heap[(i-1)>>1], heap[i]]; i = (i-1)>>1; } }
  function pop() { const top = heap[0], last = heap.pop(); if (heap.length) { heap[0] = last; let i = 0; for(;;){ const l = 2*i+1, r = 2*i+2; let m = i; if (l < heap.length && heap[l] > heap[m]) m = l; if (r < heap.length && heap[r] > heap[m]) m = r; if (m === i) break; [heap[i], heap[m]] = [heap[m], heap[i]]; i = m; } } return top; }
  for (let x of nums) { if (x % 2) x *= 2; push(x); if (x < lo) lo = x; }
  let best = heap[0] - lo;
  while (heap[0] % 2 === 0) {
    const t = pop() / 2;
    if (t < lo) lo = t;
    push(t);
    best = Math.min(best, heap[0] - lo);
  }
  return best;
}

class Solution {
    public int minimumDeviation(int[] nums) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int lo = Integer.MAX_VALUE;
        for (int x : nums) { if (x % 2 == 1) x *= 2; pq.offer(x); lo = Math.min(lo, x); }
        int best = pq.peek() - lo;
        while (pq.peek() % 2 == 0) {
            int t = pq.poll() / 2;
            lo = Math.min(lo, t);
            pq.offer(t);
            best = Math.min(best, pq.peek() - lo);
        }
        return best;
    }
}

int minimumDeviation(vector<int>& nums) {
    priority_queue<int> pq;
    int lo = INT_MAX;
    for (int x : nums) { if (x % 2) x *= 2; pq.push(x); lo = min(lo, x); }
    int best = pq.top() - lo;
    while (pq.top() % 2 == 0) {
        int t = pq.top() / 2; pq.pop();
        lo = min(lo, t); pq.push(t);
        best = min(best, pq.top() - lo);
    }
    return best;
}

Explanation

We can double odd numbers and halve even numbers, and we want to make the spread (max − min) as small as possible. The clever framing: double every odd number first, so now every value is even and the only remaining move is halving.

Doubling all odds doesn't lose any options. An odd value x could only ever be doubled once (after that it's even), so we just do that doubling up front. From here on, the only operation left is halving an even number, which can only make values smaller.

So we put all values in a max-heap and track the current min. Repeatedly we take the current maximum and halve it, since shrinking the max is the only way to shrink the spread. After each halve we update min (the halved value might become the new smallest) and record max − min as a candidate answer.

We stop when the maximum is odd, because an odd number can't be halved any further — there's no move left to reduce the top.

Example: nums=[1,2,3,4]. Double odds → [2,2,6,4]. Halving the max repeatedly passes through states like [2,2,3,4] and [2,2,3,2], where the spread becomes 1, the best achievable.

Time: O(n · log n · log max) Space: O(n)