Question
Minimum Moves to Zero
In a kingdom, a wizard has a magic number . To break the spell and turn into 0, he can perform one of two actions: add or subtract any power of 2. What’s the minimum number of moves the wizard needs to make the magic number equal to 0?
Input
The first and only line of the input contains a single integer n.
Constraints
1 ≤ n ≤ 105
Constraints
1 ≤ n ≤ 105
Output
Print minimum number of operations required to reduce the magic number to 0.
Example
Sample Input:
39
Sample Output
3
Explanation
We can do the following operations:
- Add 20 = 1 to n, so now n = 39 + 1 = 40.
- Subtract 23 = 8 from n, so now n = 40 - 8 = 32.
- Subtract 25 = 32 from n, so now n = 32 - 32 = 0.
Thus, at least 3 operations are required to reduce number to 0.
39
Sample Output
3
Explanation
We can do the following operations:
- Add 20 = 1 to n, so now n = 39 + 1 = 40.
- Subtract 23 = 8 from n, so now n = 40 - 8 = 32.
- Subtract 25 = 32 from n, so now n = 32 - 32 = 0.
Thus, at least 3 operations are required to reduce number to 0.