Power Reduction
MediumGreedy · SalesForce
You are given a non-negative integer n. In one operation you may pick any power of two, 2^i for some i >= 0 (that is, 1, 2, 4, 8, ...), and either add it to n or subtract it from n. The value may temporarily go above the original n.
Return the minimum number of operations needed to make n equal to 0.
Example 1
- Input:
- n = 23
- Output:
- 3
- Explanation
23is10111in binary. Add1to get24, subtract8to get16, then subtract16to reach0: three operations. Subtracting one bit at a time would take four.
Example 2
- Input:
- n = 15
- Output:
- 2
- Explanation
15 + 1 = 16, then16 - 16 = 0. Two operations instead of the four set bits.
Example 3
- Input:
- n = 10
- Output:
- 2
- Explanation
10is8 + 2. Subtract8and then2; no single power of two equals 10, so two is the minimum.
Constraints
- 0 ≤
n≤ 1015