Question
Minimum Steps Using Powers of Two
You are given a non-negative integer KaTeX can only parse string typed expression. In one step, you can subtract any power of 2 (i.e., KaTeX can only parse string typed expression for some integer KaTeX can only parse string typed expression) from KaTeX can only parse string typed expression, provided the result remains non-negative.
Your task is to determine the minimum number of steps required to reduce KaTeX can only parse string typed expression to exactly KaTeX can only parse string typed expression.
Input
The first line contains a single integer KaTeX can only parse string typed expression.
Output
Print a single integer — the minimum number of steps required to make KaTeX can only parse string typed expression.
Example
Input
13
Output
3
Explanation
We can subtract powers of 2 as follows:
13 → 13 - 8 = 5
5 → 5 - 4 = 1
1 → 1 - 1 = 0
Total steps = 3.
13
Output
3
Explanation
We can subtract powers of 2 as follows:
13 → 13 - 8 = 5
5 → 5 - 4 = 1
1 → 1 - 1 = 0
Total steps = 3.