Fuse the Two Lightest

Medium

A foundry holds metal bars with weights weights. Every bar should weigh at least floor. One operation takes the two lightest bars x ≤ y, removes them and puts in a single new bar of weight 2·x + y. The operation is only possible while there are at least two bars. Return the fewest operations after which every bar weighs at least floor.

Example 1

weights=[1, 6, 2, 9], floor=7 → 2

Fuse 1 and 2: 1·2 + 2 = 4, leaving [6, 4, 9]. Then 4 and 6: 4·2 + 6 = 14, leaving [9, 14], all at least 7.

Example 2

weights=[8, 12, 7], floor=7 → 0

Every bar already weighs at least 7.

Example 3

weights=[1, 1, 1], floor=5 → 2

1 and 1 give 3, leaving [1, 3]; then 1·2 + 3 = 5.

Constraints

2 ≤ len(weights) ≤ 2·10⁵
1 ≤ weights[i] ≤ 10⁹
1 ≤ floor ≤ 10⁹
The goal is always reachable

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Simulation Heap (Priority Queue)

Similar problems

Shuttle Seat Plan Medium Unfilled Exchange Orders Medium Hiring From Both Ends of the Line Medium Cross Out the Smallest First Medium Rounds of Row Maximums Medium

Input

weights=[1, 6, 2, 9], floor=7

Expected

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