Problem Description

Given an array of positive integers nums, you can perform two operations on each element:

• If the element is even, you can divide it by 2 (as many times as you want, until it becomes odd).
• If the element is odd, you can multiply it by 2 (only once).

• Each operation can be applied as many times as allowed by the rules to each element.
• Return the minimum possible deviation after applying these operations optimally.

Example:
Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2] (after dividing 4 by 2), and the deviation is 3-1=2. But you can get [2,2,3,4] (by multiplying 1 by 2), and then [2,2,3,2] (by dividing 4 by 2), and the deviation is 3-2=1, which is the minimum.

Thought Process

At first glance, you might consider brute-forcing all possible combinations by applying allowed operations to every element and checking the resulting deviations. However, this approach quickly becomes infeasible as the number of possibilities grows exponentially with the size of the array.

Instead, notice that:

• Even numbers can be reduced (by dividing by 2) until they become odd, potentially making them much smaller.
• Odd numbers can only be increased (by multiplying by 2, once), potentially making them much larger.

Solution Approach

We'll use the following step-by-step algorithm:

1. Normalize the Array:
   • For every element in nums, if it's odd, multiply it by 2 (since we can only do this once, and it gives us the maximum possible value for that element).
   • If it's even, leave it as is (since we can divide it down later).
2. Build a Max-Heap:
   • Insert all normalized elements into a max-heap (priority queue), so we can always access the current largest element efficiently.
3. Track the Minimum Value:
   • Keep track of the minimum value among all current elements, as this will help us calculate the deviation at each step.
4. Iteratively Minimize Deviation:
   • While the largest element in the heap is even, remove it, divide it by 2, and insert it back into the heap.
   • Update the minimum value if the new value is smaller.
   • At each step, compute the deviation (current max - current min) and keep track of the smallest deviation seen so far.
5. Termination:
   • When the largest element becomes odd, no further division is allowed. The process stops, and the smallest deviation found is the answer.

Example Walkthrough

Let's walk through the example nums = [1,2,3,4]:

1. Normalize:
   • 1 (odd) → 2
   • 2 (even) → 2
   • 3 (odd) → 6
   • 4 (even) → 4
   The array becomes [2, 2, 6, 4].
2. Build max-heap:
   • Heap contains [6, 4, 2, 2], min = 2
3. Iterate:
   • Pop 6 (max), deviation = 6-2=4. Divide 6 by 2 → 3. Heap: [4, 3, 2, 2], min = 2. New deviation = 4-2=2.
   • Pop 4 (max), deviation = 4-2=2. Divide 4 by 2 → 2. Heap: [3, 2, 2, 2], min = 2. New deviation = 3-2=1.
   • Pop 3 (max), now 3 is odd, cannot divide further. Stop.
4. Result: The minimum deviation encountered is 1.

Time and Space Complexity

Brute-force approach:

• Would involve generating all possible combinations of allowed operations for each element, which is exponential in the size of the array (O(2^n)), making it infeasible for large arrays.

• Each element can only be divided by 2 a limited number of times (until it becomes odd), so the number of heap operations is bounded by O(n log M), where M is the maximum value in the array.
• Each heap operation (push/pop) is O(log n), and in total, we perform O(n log M) such operations.
• Space complexity is O(n) for the heap and storing the array.

Summary

The key to minimizing deviation in the array is to maximize the flexibility of each element: make all odds as large as possible (by multiplying by 2 once) and all evens as small as possible (by dividing by 2 as much as possible). Using a max-heap allows us to efficiently and repeatedly reduce the current largest element, always tracking the minimum, until no further reductions are possible. This greedy approach ensures we always make the best move at each step, resulting in an elegant and efficient solution.

Code Implementation

import heapq

class Solution:
    def minimumDeviation(self, nums):
        # Normalize: make all numbers even (multiply odds by 2)
        heap = []
        min_num = float('inf')
        for num in nums:
            if num % 2:
                num *= 2
            heap.append(-num)  # max-heap via negative values
            min_num = min(min_num, num)
        heapq.heapify(heap)

        min_deviation = float('inf')
        while True:
            max_num = -heapq.heappop(heap)
            min_deviation = min(min_deviation, max_num - min_num)
            if max_num % 2 == 0:
                next_num = max_num // 2
                min_num = min(min_num, next_num)
                heapq.heappush(heap, -next_num)
            else:
                break
        return min_deviation
      

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        priority_queue<int> maxHeap;
        int minNum = INT_MAX;
        for (int num : nums) {
            if (num % 2 == 1) num *= 2;
            maxHeap.push(num);
            minNum = min(minNum, num);
        }
        int minDev = INT_MAX;
        while (true) {
            int maxNum = maxHeap.top(); maxHeap.pop();
            minDev = min(minDev, maxNum - minNum);
            if (maxNum % 2 == 0) {
                maxNum /= 2;
                minNum = min(minNum, maxNum);
                maxHeap.push(maxNum);
            } else {
                break;
            }
        }
        return minDev;
    }
};
      

import java.util.*;

class Solution {
    public int minimumDeviation(int[] nums) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int minNum = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num % 2 == 1) num *= 2;
            maxHeap.offer(num);
            minNum = Math.min(minNum, num);
        }
        int minDev = Integer.MAX_VALUE;
        while (true) {
            int maxNum = maxHeap.poll();
            minDev = Math.min(minDev, maxNum - minNum);
            if (maxNum % 2 == 0) {
                maxNum /= 2;
                minNum = Math.min(minNum, maxNum);
                maxHeap.offer(maxNum);
            } else {
                break;
            }
        }
        return minDev;
    }
}
      

class MaxHeap {
    constructor() {
        this.data = [];
    }
    push(val) {
        this.data.push(val);
        this._bubbleUp(this.data.length - 1);
    }
    pop() {
        if (this.data.length === 1) return this.data.pop();
        const top = this.data[0];
        this.data[0] = this.data.pop();
        this._bubbleDown(0);
        return top;
    }
    peek() {
        return this.data[0];
    }
    _bubbleUp(idx) {
        while (idx > 0) {
            const parent = Math.floor((idx - 1) / 2);
            if (this.data[parent] >= this.data[idx]) break;
            [this.data[parent], this.data[idx]] = [this.data[idx], this.data[parent]];
            idx = parent;
        }
    }
    _bubbleDown(idx) {
        const n = this.data.length;
        while (true) {
            let largest = idx;
            let left = 2 * idx + 1;
            let right = 2 * idx + 2;
            if (left < n && this.data[left] > this.data[largest]) largest = left;
            if (right < n && this.data[right] > this.data[largest]) largest = right;
            if (largest === idx) break;
            [this.data[idx], this.data[largest]] = [this.data[largest], this.data[idx]];
            idx = largest;
        }
    }
}

var minimumDeviation = function(nums) {
    let heap = new MaxHeap();
    let minNum = Infinity;
    for (let num of nums) {
        if (num % 2 === 1) num *= 2;
        heap.push(num);
        minNum = Math.min(minNum, num);
    }
    let minDev = Infinity;
    while (true) {
        let maxNum = heap.pop();
        minDev = Math.min(minDev, maxNum - minNum);
        if (maxNum % 2 === 0) {
            maxNum = Math.floor(maxNum / 2);
            minNum = Math.min(minNum, maxNum);
            heap.push(maxNum);
        } else {
            break;
        }
    }
    return minDev;
};