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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimize Deviation in Array

Number: 1794

Difficulty: Hard

Paid? No

Companies: Apple, Samsung

Problem Description

Given an array of positive integers, you can perform the following operations any number of times on any element:

  • If an element is even, you may divide it by 2.
  • If an element is odd, you may multiply it by 2.

The goal is to minimize the deviation, defined as the difference between the maximum and minimum values in the array after applying any sequence of operations.

Key Insights

  • Convert all odd numbers to even by multiplying them by 2, because only even numbers can be reduced.
  • Use a max-heap (or simulate one) for efficiently retrieving the current maximum element.
  • Track the minimum number seen so far across the transformed array.
  • Repeatedly extract the maximum element and if it is even, divide it by 2, update the deviation and the minimum accordingly, and push the new value back into the heap.
  • Terminate when the maximum element becomes odd (cannot be reduced further), as no further reduction on that element is allowed.

Space and Time Complexity

Time Complexity: O(n * log(m)), where m is the range determined by the maximum element after conversion. Each heap operation takes O(log n) and each element might undergo O(log(max_num)) divisions. Space Complexity: O(n) for maintaining the heap.

Solution

The solution starts by transforming all numbers: every odd number is multiplied by 2 to make it even. This ensures that every number can only decrease (by dividing by 2). Use a max-heap to always extract the current maximum element. Also, maintain a variable to track the minimum value in the heap. At each iteration, update the deviation (max - min) and if the maximum is even, reduce it by half and update the minimum if necessary. Continue until the maximum element cannot be reduced further (i.e., it is odd). This greedy approach guarantees that we search over all effective transformations to minimize the overall deviation.

Code Solutions

import heapq

def minimumDeviation(nums):
    # Initialize a max heap using negatives, and track the minimum element.
    heap = []
    min_val = float('inf')
    
    # Step 1: Convert odd numbers to even numbers and add them to the heap.
    for num in nums:
        # if odd, multiply by 2 to make even.
        if num % 2:
            num *= 2
        # Update the minimum element.
        min_val = min(min_val, num)
        # Push the negative to simulate max-heap.
        heapq.heappush(heap, -num)
    
    # Initialize the minimum deviation.
    min_deviation = float('inf')
    
    # Step 2: Process the heap.
    while heap:
        # Extract the current maximum element.
        curr_max = -heapq.heappop(heap)
        # Update the minimum deviation.
        min_deviation = min(min_deviation, curr_max - min_val)
        
        # If current maximum is even, we can reduce it.
        if curr_max % 2 == 0:
            next_val = curr_max // 2
            # Update the global minimum.
            min_val = min(min_val, next_val)
            # Push new value back into heap.
            heapq.heappush(heap, -next_val)
        else:
            # If it's odd, no more reduction is possible.
            break
    
    return min_deviation

# Example usage:
print(minimumDeviation([1,2,3,4]))
← Back to All Questions