Question
Spell Shift
In a mystical realm, Sage holds a charmed number. To dispel it and reach 0, he can add or subtract any power of 2. Find the minimum number of moves needed to make the charmed number 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.