Question
Shortest Path between Cities
Geek lives in a special city where houses are arranged in a hierarchical manner. Starting from house number 1, each house leads to two more houses.
1 leads to 2 and 3.
2 leads to 4 and 5.
3 leads to 6 and 7. and so on.
Given the house numbers on two houses x and y, find the length of the shortest path between them.
1 leads to 2 and 3.
2 leads to 4 and 5.
3 leads to 6 and 7. and so on.
Given the house numbers on two houses x and y, find the length of the shortest path between them.
1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15
Input
There is a single line of input taking two space-separated integers representing x and y respectively.
Constraints:
1 ≤ x,y ≤ 109
Constraints:
1 ≤ x,y ≤ 109
Output
Print a single integer representing the length of the shortest path between them.
Example
Input:
2 6
Output:
3
Explanation:
x = 2, y = 6
The length of the shortest path between 2 and 6 is 3. ie 2-> 1-> 3-> 6.
Input:
8 10
Output:
4
Explanation:
x = 8, y = 10
8-> 4-> 2-> 5-> 10
The length of the shortest path between 8 and 10 is 4.
2 6
Output:
3
Explanation:
x = 2, y = 6
The length of the shortest path between 2 and 6 is 3. ie 2-> 1-> 3-> 6.
Input:
8 10
Output:
4
Explanation:
x = 8, y = 10
8-> 4-> 2-> 5-> 10
The length of the shortest path between 8 and 10 is 4.