Minimize Deviation in Array

Problem

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.

Examples

Example 1:

1
2
3
4
5


Input:
nums = [1,2,3,4]
Output:
 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

Example 2:

1
2
3
4
5


Input:
nums = [4,1,5,20,3]
Output:
 3
Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.

Example 3:

1
2
3
4


Input:
nums = [2,10,8]
Output:
 3

Solution

Method 1 – Greedy with Max-Heap

Intuition

The key idea is to maximize the minimum value and minimize the maximum value in the array. By always reducing the current maximum (by dividing even numbers by 2), we can try to bring all numbers closer together. Odd numbers can only be increased once (by multiplying by 2), so we first normalize all numbers to their possible maximums, then repeatedly reduce the largest.

Approach

For each number in nums, if it’s odd, multiply by 2 (so all numbers are even and can be reduced).
Insert all numbers into a max-heap.
Track the minimum value among all numbers.
While the maximum number is even:

Pop the maximum from the heap.
Update the answer with the difference between max and min.
Divide the max by 2 and push it back.
Update the minimum if needed.

After the loop, check the final deviation.
Return the minimum deviation found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
public:
   int minimumDeviation(vector<int>& nums) {
      priority_queue<int> pq;
      int mn = INT_MAX, ans = INT_MAX;
      for (int n : nums) {
        if (n % 2) n *= 2;
        pq.push(n);
        mn = min(mn, n);
      }
      while (pq.top() % 2 == 0) {
        int mx = pq.top(); pq.pop();
        ans = min(ans, mx - mn);
        mx /= 2;
        pq.push(mx);
        mn = min(mn, mx);
      }
      ans = min(ans, pq.top() - mn);
      return ans;
   }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


func minimumDeviation(nums []int) int {
   h := &IntHeap{}
   mn := int(1e9)
   for _, n := range nums {
      if n%2 == 1 {
        n *= 2
      }
      heap.Push(h, -n)
      if n < mn {
        mn = n
      }
   }
   ans := int(1e9)
   for {
      mx := -heap.Pop(h).(int)
      if ans > mx-mn {
        ans = mx - mn
      }
      if mx%2 == 1 {
        break
      }
      mx /= 2
      if mx < mn {
        mn = mx
      }
      heap.Push(h, -mx)
   }
   return ans
}

// IntHeap implements heap.Interface for negative values (max-heap)
type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
   old := *h
   n := len(old)
   x := old[n-1]
   *h = old[:n-1]
   return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
   fun minimumDeviation(nums: IntArray): Int {
      val pq = java.util.PriorityQueue<Int>(compareByDescending { it })
      var mn = Int.MAX_VALUE
      for (n in nums) {
        val v = if (n % 2 == 1) n * 2 else n
        pq.add(v)
        mn = minOf(mn, v)
      }
      var ans = Int.MAX_VALUE
      while (pq.peek() % 2 == 0) {
        val mx = pq.poll()
        ans = minOf(ans, mx - mn)
        val half = mx / 2
        pq.add(half)
        mn = minOf(mn, half)
      }
      ans = minOf(ans, pq.peek() - mn)
      return ans
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
   def minimumDeviation(self, nums: list[int]) -> int:
      import heapq
      h: list[int] = []
      mn: int = float('inf')
      for n in nums:
        if n % 2:
           n *= 2
        heapq.heappush(h, -n)
        mn = min(mn, n)
      ans: int = float('inf')
      while True:
        mx = -heapq.heappop(h)
        ans = min(ans, mx - mn)
        if mx % 2:
           break
        mx //= 2
        mn = min(mn, mx)
        heapq.heappush(h, -mx)
      return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


impl Solution {
   pub fn minimum_deviation(nums: Vec<i32>) -> i32 {
      use std::collections::BinaryHeap;
      let mut heap = BinaryHeap::new();
      let mut mn = i32::MAX;
      for mut n in nums {
        if n % 2 == 1 { n *= 2; }
        heap.push(n);
        mn = mn.min(n);
      }
      let mut ans = i32::MAX;
      while let Some(mx) = heap.peek().copied() {
        ans = ans.min(mx - mn);
        if mx % 2 == 1 { break; }
        let mx = heap.pop().unwrap() / 2;
        mn = mn.min(mx);
        heap.push(mx);
      }
      ans
   }
}

Complexity

Time complexity: O(N log N) (each heap operation is log N, up to 2 * N operations)
Space complexity: O(N) (for the heap)

Problem#

Examples#

Solution#

Method 1 – Greedy with Max-Heap#

Intuition#

Approach#

Code#

Complexity#