Minimize Deviation in Array

Hard

Samsung

0 views

Topics:

ArraysGreedy Algorithms

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.

Example 1:

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:

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:

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

Constraints:

n == nums.length
2 <= n <= 5 * 10⁴
1 <= nums[i] <= 10⁹

Minimize Deviation in Array

Hard

Samsung

0 views

Topics:

ArraysGreedy Algorithms

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.

Example 1:

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:

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:

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

Constraints:

n == nums.length
2 <= n <= 5 * 10⁴
1 <= nums[i] <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values within the array?
Can the input array contain zero or negative numbers?
What should I return if the input array is empty or null?
Are duplicate values allowed within the array, and if so, how should they be handled?
Is the goal to minimize the *absolute* deviation, or some other measure, like the squared deviation?

Brute Force Solution

Approach

The brute force method for this problem involves checking every possible combination of changes to our numbers. We want to find the smallest difference between the biggest and smallest number after doing some changes. We'll explore all possible changes, one at a time.

Here's how the algorithm would work step-by-step:

First, we go through each number and try doubling it, if it's odd. This creates one set of numbers to consider.
Then, we try halving the even numbers, one at a time, until they become odd.
We calculate the difference between the largest and smallest number in this new set. This difference is a 'deviation'.
Now, we repeat this process, trying all possible combinations of doubling odd numbers and halving even numbers.
Each time we get a new set of numbers, we calculate the deviation and compare it to the smallest deviation we've seen so far.
We keep track of the smallest deviation found across all the combinations we've tried.
After trying every possible combination of changes, the smallest deviation we've recorded is our answer.

Code Implementation

def minimize_deviation_brute_force(numbers):
    min_deviation = float('inf')

    def calculate_deviation(current_numbers):
        return max(current_numbers) - min(current_numbers)

    def backtrack(index, current_numbers):
        nonlocal min_deviation

        min_deviation = min(min_deviation, calculate_deviation(current_numbers))

        if index == len(numbers):
            return

        original_number = numbers[index]
        current_number = current_numbers[index]

        # Explore doubling if odd
        if original_number % 2 != 0:
            doubled_numbers = current_numbers[:]
            doubled_numbers[index] = original_number * 2
            backtrack(index + 1, doubled_numbers)

        # Explore halving if even
        if current_number % 2 == 0:
            halved_numbers = current_numbers[:]
            halved_numbers[index] = current_number // 2
            # Only proceed if halving leads to deviation decrease
            if calculate_deviation(halved_numbers) < calculate_deviation(current_numbers):
                backtrack(index + 1, halved_numbers)
        
        # If the number is even after doubling or halving, further explore
        if current_number != original_number and current_number % 2 == 0:
            halved_numbers = current_numbers[:]
            halved_numbers[index] = current_number // 2
            # Only proceed if halving leads to deviation decrease
            if calculate_deviation(halved_numbers) < calculate_deviation(current_numbers):
                backtrack(index + 1, halved_numbers)

        backtrack(index + 1, current_numbers)

    backtrack(0, numbers[:])

    return min_deviation

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^(n*m)) – The brute force approach involves exploring all possible combinations of doubling odd numbers and halving even numbers. For each number, we can either leave it as is, double it once (if odd), or halve it repeatedly (if even) until it becomes odd. In the worst case, we might have n numbers and each number can be halved a maximum of m times, where m is related to the maximum value in the input. Each number has two possibilities (leave it as is or double if odd) or a variable number of possibilities (halve repeatedly until odd). Considering the worst-case combinations, the total number of combinations we need to evaluate is exponential, specifically O(2^(n*m)), where n is the number of elements and m represents the maximum possible halving operations for an element. We need to consider all the subsets of the transformed numbers.

Space Complexity

O(1) – The brute force solution, as described, primarily modifies the input array in place. While it explores different combinations of doubling and halving numbers, it doesn't explicitly create auxiliary data structures that scale with the input size (N, where N is the number of elements in the array). The smallest deviation found is stored in a single variable. Therefore, the auxiliary space required is constant, independent of the size of the input array.

Optimal Solution

Approach

The key idea is to focus on reducing the largest number and increasing the smallest number in the given collection. By strategically applying allowable operations, we bring the numbers closer together, which shrinks the difference between the largest and smallest.

Here's how the algorithm would work step-by-step:

First, try to make all the odd numbers even by doubling them. This is because doubling an odd number gets it closer to the larger even numbers.
Next, find the largest number in your collection.
If the largest number is even, try to divide it by two to make it smaller. Keep doing this as long as the largest number remains even.
Keep track of both the largest and smallest numbers as they change, and calculate the difference between them.
Repeat steps 2-4 until no even numbers are remaining and can be further divided. This means you've done as much as you can to minimize the difference.

Code Implementation

def minimize_deviation(nums):
    numbers_set = set()
    for number in nums:
        if number % 2 != 0:
            numbers_set.add(number * 2)
        else:
            numbers_set.add(number)

    deviation = float('inf')

    # The smallest number.
    smallest_number = min(numbers_set)

    # We repeatedly reduce the largest number.
    while True:
        largest_number = max(numbers_set)
        deviation = min(deviation, largest_number - smallest_number)

        # If the largest number is even, we can halve it.
        if largest_number % 2 == 0:
            numbers_set.remove(largest_number)
            numbers_set.add(largest_number // 2)
            smallest_number = min(numbers_set)

        # Otherwise, we can't reduce further.
        else:
            break

    return deviation

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – Initially, we iterate through the n elements of the array to double any odd numbers, which takes O(n) time. The core of the algorithm involves repeatedly finding the maximum element (which, if even, we divide by 2) and updating the minimum. Using a heap (like a priority queue) to store the numbers allows us to find the maximum in O(1) time and update the heap in O(log n) time. We might perform the division operation at most log k times for each element, where k is the initial maximum value in the array, giving us a bound of O(n log k) for the heap operations. Since log k is usually smaller than or equal to log n, the overall time complexity is dominated by heap construction plus the potential divisions, approximating to O(n log n).

Space Complexity

O(N) – The described algorithm implicitly modifies the input array in-place to convert odd numbers to even numbers initially, however, it utilizes a heap (or similar priority queue structure) to efficiently track the largest and smallest numbers. Since, in the worst-case, all numbers in the input array nums need to be stored in the heap, the auxiliary space complexity is proportional to the number of elements in the input array (N). Thus, the space complexity of the solution is O(N) where N is the number of elements in the input array.

Edge Cases

Case	How to Handle
Empty input array	Return infinity or an error, as no deviation can be calculated.
Array with only one element	Return 0, as there's only one number and no deviation.
Array with all identical elements	The deviation will be 0, as the maximum and minimum are the same.
Array with large numbers leading to potential integer overflow when doubling	Use a data type that can handle larger values, such as long, to prevent overflow.
Array where all even numbers are at their minimum and all odd numbers are at their maximum possible values after operations.	The deviation is minimized when all numbers are close to each other, so calculate the deviation after even number division and odd number multiplication.
Array with a very skewed distribution of numbers (e.g., one very large number and many small numbers)	The maximum deviation can be very large, potentially affecting performance and requiring careful handling of data types.
Maximum sized input array	Ensure that the algorithm's time and space complexity are efficient enough to handle large inputs.
Array contains negative numbers	Convert all numbers to positive during initial step by getting their absolute value to avoid unexpected results.