560. Minimize Deviation in Array

HardBinary SearchHeapGreedy

Given an array of positive integers, you may repeatedly perform either operation any number of times on any element: if it is even, divide it by 2; if it is odd, multiply it by 2. The deviation is the difference between the maximum and minimum elements. Return the minimum possible deviation. Input: an array of positive integers.

Input: An array of positive integers.

Output: Integer — the minimum deviation.

Examples

Example 1
Input: [1,2,3,4]
Output: 1
Explanation: Transform to bring max and min within 1.
Example 2
Input: [4,1,5,20,3]
Output: 3
Explanation: Minimum achievable spread.
Example 3
Input: [2,10,8]
Output: 3
Explanation: Best deviation is 3.

Constraints

Asked by

Amazon
Solve this problem in the editor →