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.