We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimize Deviation in Array

Difficulty: Hard

Problem Description

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. Return the minimum deviation the array can have after performing some number of operations.

Key Insights

  • Even numbers can be reduced, while odd numbers can be increased.
  • The goal is to minimize the difference between the maximum and minimum elements in the array.
  • Using a max-heap allows for efficient retrieval of the current maximum value in the array.
  • Continuously reducing the maximum value and adjusting the minimum value leads to finding the optimal deviation.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

To solve this problem, we can utilize a max-heap (priority queue) to keep track of the maximum element in the array. First, we transform all numbers: if they are even, we add them to the heap as is; if they are odd, we multiply them by 2 before adding them to the heap. The algorithm then repeatedly extracts the maximum element, reduces it by dividing by 2, and checks if the new maximum leads to a smaller deviation. This process continues until the maximum element is odd, ensuring we maintain operations on the even numbers only. Finally, we calculate the deviation between the current maximum and minimum values.

Code Solutions

import heapq

def minimumDeviation(nums):
    # Initialize a max-heap
    max_heap = []
    min_value = float('inf')
    
    # Populate the max-heap and find the initial minimum value
    for num in nums:
        if num % 2 == 1:
            num *= 2  # Make odd numbers even
        heapq.heappush(max_heap, -num)  # Use negative to simulate max-heap
        min_value = min(min_value, num)
    
    min_deviation = float('inf')
    
    # Process the heap
    while max_heap:
        max_value = -heapq.heappop(max_heap)  # Get the maximum value
        min_deviation = min(min_deviation, max_value - min_value)  # Update the minimum deviation
        
        if max_value % 2 == 1:  # If max_value is odd, we cannot divide it further
            break
        
        # Divide the maximum value by 2 and push it back to the heap
        new_value = max_value // 2
        heapq.heappush(max_heap, -new_value)  # Push the new value as negative
        min_value = min(min_value, new_value)  # Update the minimum value if necessary

    return min_deviation
← Back to All Questions