#2571
Minimum Operations to Reduce an Integer to 0
specialist · 720 · lc medium +30 · verified · 61.2% accepted · 620 likes · top 61%
Description
Given a positive integer n, in each operation you may add or subtract any power of 2. Return the minimum number of operations needed to reduce n to 0.
Example 1:
Input: n = 39
Output: 3
Explanation: We can do the following operations:
- Add 20 = 1 to n, so now n = 40.
- Subtract 23 = 8 from n, so now n = 32.
- Subtract 25 = 32 from n, so now n = 0.
It can be shown that 3 is the minimum number of operations we need to make n equal to 0.
Example 2:
Input: n = 54
Output: 3
Explanation: We can do the following operations:
- Add 21 = 2 to n, so now n = 56.
- Add 23 = 8 to n, so now n = 64.
- Subtract 26 = 64 from n, so now n = 0.
So the minimum number of operations is 3.
Code
1
2
3