# Minimize Deviation in Array

##### December 28, 2023

## 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. If the element is odd, multiply it by 2. The deviation of the array is the maximum difference between any two elements in the array. Find the minimum deviation the array can have after performing some number of operations.

## Solution #

Here’s the Python code to find the minimum possible deviation in an array of positive integers by performing operations to either halve even numbers or double odd numbers:

```
import heapq
def minimum_deviation(nums):
"""
Find the minimum deviation possible in the array nums by performing operations
to either halve even numbers or double odd numbers.
:param nums: List of positive integers
:return: The minimum possible deviation
"""
# Convert all numbers to potential maximum values and add to a min heap
heap = []
for num in nums:
heapq.heappush(heap, -num * 2 if num % 2 else -num)
# The current maximum deviation is the difference between the smallest and largest elements
max_num = -min(heap)
deviation = max_num - (-max(heap))
# Try to minimize the deviation by halving the maximum elements
while -heap[0] % 2 == 0: # While the maximum element is even
max_num = -heapq.heappop(heap) // 2 # Halve it
heapq.heappush(heap, -max_num)
deviation = min(deviation, max_num - (-max(heap))) # Update the deviation
return deviation
# Example usage
nums = [1, 2, 3, 4]
minimum_deviation(nums)
```

This code first transforms all numbers to their potential maximum values (if odd, double them; if even, keep them as is) and then adds them to a min heap. The process aims to minimize the deviation, which is the difference between the largest and smallest elements in the heap. It iteratively halves the largest element (if even) and recalculates the deviation. The loop continues until the largest element is odd, at which point no further minimization can be achieved.

For example, with the input `nums = [1, 2, 3, 4]`

, the function will return the minimum possible deviation after performing the specified operations.