Question
Minimum Steps to Reach Target
You are given an integer target. Your task is to find the minimum number of steps required to reach the target by starting from 0 and applying the following two operations:
- Double: You can multiply the current number by 2.
- Increment: You can add 1 from the current number.
Input
The first and only line of input contains an integer representing the target number to reach.
Constraints
1 <= 109
Constraints
1 <= 109
Output
Print an integer representing the minimum number of steps required to reach the target.
Example
Input
3
Output
3
Explanation
Start with 0, add 1, double it to get 2, and then add 1 to reach 3 in total 3 steps.
Input
4
Output
3
Explanation
Start with 0, add 1, double it to get 2, and then again double it to reach 4 in total 3 steps.
3
Output
3
Explanation
Start with 0, add 1, double it to get 2, and then add 1 to reach 3 in total 3 steps.
Input
4
Output
3
Explanation
Start with 0, add 1, double it to get 2, and then again double it to reach 4 in total 3 steps.