1392. Shortest Path in Binary Tree via XOR

Consider the infinite binary tree whose nodes are labelled 1, 2, 3, ... so that node v has children 2v and 2v+1 and parent v/2 (integer division). Given two node labels a and b, return the number of edges on the shortest path between them.

Input: A JSON object {"a": <node label>, "b": <node label>}.

Output: Return the edge distance between nodes a and b.

Examples

Input: {"a":4,"b":5}
Output: 2
Explanation: Both rise to node 2 in one step each -> 2.

Input: {"a":1,"b":8}
Output: 3
Explanation: Node 8 climbs to the root in three steps -> 3.

Constraints

• 1 <= a, b <= 10^15

Asked by