Halve or Double

Hard

You are given an array of positive integers values. Any element may be changed any number of times with one of two moves: - if the number is **even**, divide it by 2; - if the number is **odd**, multiply it by 2. The **spread** of the array is the difference between its largest and smallest elements. Return the smallest spread you can reach with these moves.

Example 1

values=[6, 3, 10] → 1

Double the 3 into 6 and halve the 10 into 5: the array becomes [6, 6, 5] with a spread of 6 − 5 = 1. A spread of 0 is impossible: 10 can only be 10 or 5, and 3 can only be 3 or 6.

Example 2

values=[7, 28] → 0

Halve 28 twice to get 7, and the two numbers are equal.

Example 3

values=[5, 9, 40] → 1

Constraints

2 ≤ len(values) ≤ 5·10⁴
1 ≤ values[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Ordered Set Heap (Priority Queue)

Similar problems

Busiest Workers in a Ring Hard City Block Outline Hard Growing Capital Project by Project Hard Most Orders by Their Deadlines Hard Narrowest Range Touching Every List Hard

Input

values=[6, 3, 10]

Expected

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.