Question
Minimum Energy Injection
You are operating a futuristic Energy Reactor that starts with zero energy units.
The reactor works in daily cycles:
-
At the start of each day, you may inject any number of energy units into the reactor.
-
At the end of the day, the reactor automatically doubles the total energy currently stored.
You may choose to inject zero energy on any day.
Your task is to determine the minimum total number of energy units injected (across all days) such that the reactor ends up with exactly KaTeX can only parse string typed expression energy units after some number of days.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the target amount of energy in the reactor.
Output
Print a single integer — the minimum total energy units injected to reach exactly KaTeX can only parse string typed expression energy units.
Example
Input
13
Output
3
Explanation
We want the reactor to contain exactly 13 energy units.
Day 1: Inject 1 → total becomes 1 → doubles to 2
Day 2: Inject 1 → total becomes 3 → doubles to 6
Day 3: Inject 0 → total stays 6 → doubles to 12
Day 4: Inject 1 → total becomes 13 → stop
Total injected energy = 1 + 1 + 0 + 1 = 3
Input
8
Output
1
Explanation
Day 1: Inject 1 → total becomes 1
Let the reactor double automatically: 1 → 2 → 4 → 8
Only 1 unit was injected in total.
13
Output
3
Explanation
We want the reactor to contain exactly 13 energy units.
Day 1: Inject 1 → total becomes 1 → doubles to 2
Day 2: Inject 1 → total becomes 3 → doubles to 6
Day 3: Inject 0 → total stays 6 → doubles to 12
Day 4: Inject 1 → total becomes 13 → stop
Total injected energy = 1 + 1 + 0 + 1 = 3
Input
8
Output
1
Explanation
Day 1: Inject 1 → total becomes 1
Let the reactor double automatically: 1 → 2 → 4 → 8
Only 1 unit was injected in total.