Operations to Reach Goal Number
Statement
Goal
You begin with a number N. You can do one of two operations:Operation 1: Divide the number N by 2 (Note that if N is odd this would not result in an integer, and it would be impossible to reach 1)
Operation 2: Subtract 1 from N
However, you only can do operation 1, dividing N by 2, a maximum of A times.
You want to reach the number 1 in the minimum operations. Print X, the lowest number of operations it takes.
Input
Line 1: An integer N, the starting number.
Line 2: An integer A, the max times you can divide by 2.
Line 2: An integer A, the max times you can divide by 2.
Output
Output X, an integer.
Constraints
0 <= x < N <= 10^9+7
Example
Input
5 0
Output
4
Game modes
Fastest, Shortest
Test cases
Easy Test
Input
5
0
Output
4
Validator 1 Validator
Input
4
0
Output
3
Also easy Test
Input
2
2
Output
1
Validator 2 Validator
Input
4
2
Output
2
Larger Numbers Test
Input
60
1
Output
30
Validator 3 Validator
Input
129
5
Output
9
Harder Test
Input
200000
10
Output
206
Validator 4 Validator
Input
12345678
8
Output
48236
Better have optimized code Test
Input
1000000000
20
Output
978
Validator 5 Validator
Input
2147000
2
Output
536751
Optimized code check #2 Test
Input
123456789
0
Output
123456788
Validator 6 Validator
Input
1273612
1
Output
636806
Solution language
Solution
Stub generator input