Minimize Deviation in Array
01 · Problem
You are given an array nums of positive integers. You may apply the following moves to any element, as many times as you like and in any order:
- If the element is even, replace it with half of itself.
- If the element is odd, replace it with double itself.
The deviation of the array is its maximum element minus its minimum element. Return the smallest deviation you can reach.
02 · Examples
nums = [1,2,3,4]
1
Double the 1 and halve the 4 to get [2,2,3,2]. The largest value is 3 and the smallest is 2, so the deviation is 1. A deviation of 0 is impossible because 3 can only be 3 or 6.
nums = [3,5]
1
Double 3 into 6 and leave 5 alone. The array [6,5] has deviation 6 - 5 = 1, and the deviation can never be 0 because no reachable value of 3 (3 or 6) equals a reachable value of 5 (5 or 10).
nums = [4,1,5,20,3]
3
One optimal result is [2,2,5,5,3] (halve 4, double 1, halve 20 twice), with deviation 5 - 2 = 3.
03 · Constraints
- 012 <= nums.length <= 5 * 104
- 021 <= nums[i] <= 109
- 03Each operation may be applied to any element any number of times
04 · Optimal complexity
- Time
- O(n log n log M)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.