Bump One or Double All

Medium

A scoreboard shows a row of counters, all starting at zero. Its remote has two buttons: - **bump** adds 1 to a single counter of your choice; - **double** multiplies every counter by 2 at once. Each button press counts as one move. Given the array target with the value each counter must show at the end, return the fewest presses needed to reach exactly target.

Example 1

target=[3, 4] → 5

[0, 0] → +1 on the second: [0, 1] → double: [0, 2] → +1 on the first: [1, 2] → double: [2, 4] → +1 on the first: [3, 4]. Five presses in total.

Example 2

target=[0, 0, 7] → 5

[0, 0, 1] → double → [0, 0, 2] → [0, 0, 3] → double → [0, 0, 6] → [0, 0, 7]: three bumps and two doublings.

Example 3

target=[8] → 4

One bump and three doublings: 1 → 2 → 4 → 8.

Constraints

1 ≤ len(target) ≤ 10⁵
0 ≤ target[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Bit Manipulation Array

Similar problems

Best Binary Rows After Flips Medium Groups of Four at the Cinema Medium Doubling for the Biggest OR Medium Strongest Product Team Medium Most Pieces With the Smallest AND Total Medium

Input

target=[3, 4]

Expected

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