Minimum Operations to Reduce an Integer to 0
You are given a positive integer n. You can perform the following operation any number of times:
- Add or subtract a power of
2fromn.
Return the minimum number of operations needed to make n equal to 0.
A number x is a power of 2 if x == 2^i where i >= 0.
Example 1
Input
n = 39Output
3Adding 1 gives 40, then subtracting 8 gives 32, and subtracting 32 gives 0; it can be shown that 3 operations is the minimum.
Example 2
Input
n = 54Output
3Adding 2 gives 56, then adding 8 gives 64, and subtracting 64 gives 0, so the minimum number of operations is 3.
Constraints
- 1 <= n <= 10^5