Minimize Deviation in Array
HardPrompt
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].
- For example, if the array is
- 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].
- For example, if the array is
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.length2 <= n <= 5 * 1041 <= nums[i] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores every single possible configuration of the array. For each number in the input array, we first generate all the values it can be transformed into. Then, using recursion (backtracking), we try every combination of picking one value for each original number. For each complete combination, we compute its deviation and keep track of the minimum deviation seen across all combinations.
Algorithm
- For each number
nums[i]in the input array, generate a list of all its possible values. An odd numberxcan becomexor2x. An even numberycan become any value in the sequencey, y/2, y/4, ...until it becomes odd. - Use a recursive backtracking function, say
findMinDeviation(index, currentCombination), to explore all possible arrays that can be formed. - The function takes the current index
indexto be filled and thecurrentCombinationof numbers chosen so far. - Base Case: If
indexequals the length of the array, it means we have a complete combination. Calculate the deviation (max - min) for this combination and update the global minimum deviation found so far. - Recursive Step: For the number at
nums[index], iterate through all its possible values. For each possible valuev, add it to thecurrentCombinationand make a recursive call for the next index:findMinDeviation(index + 1, currentCombination). Remember to backtrack by removingvafter the recursive call returns.
Walkthrough
The brute-force method systematically generates all potential arrays that can be formed by applying the allowed operations. It's a straightforward translation of the problem statement but computationally infeasible for the given constraints.
class Solution { int minDeviation = Integer.MAX_VALUE; java.util.List<java.util.List<Integer>> possibleValues; public int minimumDeviation(int[] nums) { possibleValues = new java.util.ArrayList<>(); for (int num : nums) { java.util.Set<Integer> values = new java.util.HashSet<>(); if (num % 2 == 1) { values.add(num); values.add(num * 2); } else { int current = num; while (current % 2 == 0) { values.add(current); current /= 2; } values.add(current); } possibleValues.add(new java.util.ArrayList<>(values)); } backtrack(0, new java.util.ArrayList<>()); return minDeviation; } private void backtrack(int index, java.util.List<Integer> currentCombination) { if (index == possibleValues.size()) { if (currentCombination.isEmpty()) return; int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for (int val : currentCombination) { min = Math.min(min, val); max = Math.max(max, val); } minDeviation = Math.min(minDeviation, max - min); return; } for (int val : possibleValues.get(index)) { currentCombination.add(val); backtrack(index + 1, currentCombination); currentCombination.remove(currentCombination.size() - 1); } }}Complexity
Time
O(Π |S_i|), where |S_i| is the number of possible values for `nums[i]`. Since |S_i| can be up to `O(log M)` where `M` is the value of the number, this complexity is exponential in `N` and thus not practical.
Space
O(N + T), where `N` is the number of elements and `T` is the total number of possible values across all elements. `O(N)` for the recursion stack depth and `O(T)` to store all possible values.
Trade-offs
Pros
Conceptually simple and directly follows the problem definition.
Cons
Extremely inefficient and will time out on constraints specified in the problem.
The number of combinations grows exponentially with the number of elements
n.
Solutions
Solution
class Solution {public int minimumDeviation(int[] nums) { PriorityQueue<Integer> q = new PriorityQueue<>((a, b)->b - a); int mi = Integer.MAX_VALUE; for (int v : nums) { if (v % 2 == 1) { v <<= 1; } q.offer(v); mi = Math.min(mi, v); } int ans = q.peek() - mi; while (q.peek() % 2 == 0) { int x = q.poll() / 2; q.offer(x); mi = Math.min(mi, x); ans = Math.min(ans, q.peek() - mi); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.