Geek lives in a special city where houses are arranged in a hierarchial 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. 
Example 1:
Input:
x = 2, y = 6
Output: 3
Explanation:
              1
          /      \
        /          \
       2             3
     /   \         /   \
    4     5       6     7         
   / \   / \     / \   / \
  8  9  10 11   12 13 14 15
The length of the shortest path between 2 
and 6 is 3. ie 2-> 1-> 3-> 6.
Example 2:
Input:
x = 8, y = 10
Output: 4
Explanation: 8-> 4-> 2-> 5-> 10
The length of the shortest path between 8 
and 10 is 4. 
Your Task:
You don't need to read input or print anything. Complete the function shortestPath() which takes integers x and y as input parameters and returns the length of the shortest path from x to y.
Expected Time Complexity: O(log(max(x,y)))
Expected Auxiliary Space: O(1)
Constraints: 
1 <= x,y <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def shortestPath(self, x, y): 

        # code here

Solutions:
class Solution:

	def shortestPath(self, a, b):
		ans = 0
		y = max(a, b)
		x = min(a, b)
		while y > x:
			y = y // 2
			ans += 1
			if x > y:
				x = x // 2
				ans += 1
		return ans


class Solution:

	def shortestPath(self, x, y):
		count = 0
		while x != y:
			if x > y:
				x //= 2
			else:
				y //= 2
			count += 1
		return count


class Solution:

	def shortestPath(self, x, y):
		count = 0
		while x != y:
			while x > 1 and x > y:
				x = x // 2
				count += 1
			if x == y:
				break
			while y > 1 and y > x:
				y = y // 2
				count += 1
		return count


class Solution:

	def shortestPath(self, x, y):
		ax = []
		while x:
			ax.append(x)
			x >>= 1
		ay = []
		while y:
			ay.append(y)
			y >>= 1
		while ax[-1] == ay[-1]:
			(ax.pop(), ay.pop())
			if not ax or not ay:
				break
		return len(ax) + len(ay)


import heapq

class Solution:

	def shortestPath(self, x, y):
		heap = []
		heapq.heapify(heap)
		l1 = 0
		l2 = 0
		while x != y:
			if x / 2 >= y or x / 2 >= y - 1:
				l1 += 1
				if x % 2 == 0:
					x = int(x / 2)
				else:
					x = int((x - 1) / 2)
			elif y / 2 >= x or y / 2 >= x - 1:
				if y % 2 == 0:
					y = int(y / 2)
				else:
					y = int((y - 1) / 2)
				l2 += 1
			else:
				if x % 2 == 0:
					x = int(x / 2)
					l1 += 1
				else:
					x = int((x - 1) / 2)
					l1 += 1
				if y % 2 == 0:
					y = int(y / 2)
					l2 += 1
				else:
					y = int((y - 1) / 2)
					l2 += 1
		return l1 + l2


class Solution:

	def shortestPath(self, x, y):
		a = 0
		b = 0
		while x != y:
			if x < y:
				y = y // 2
				a += 1
			else:
				x = x // 2
				b += 1
		return a + b


class Solution:

	def shortestPath(self, x, y):
		path_x = 0
		path_y = 0
		while x != y:
			if y != 1 and y > x:
				while x != y:
					y //= 2
					path_y += 1
					break
			if x != 1 and x > y:
				while x != y:
					x //= 2
					path_x += 1
					break
		return path_x + path_y


class Solution:

	def pathTo(self, node):
		path = []
		while node >= 1:
			path.append(node)
			node = node // 2
		return path[::-1]

	def shortestPath(self, x, y):
		if x == y:
			return 0
		if x // 2 == y or y // 2 == x:
			return 1
		pathx = self.pathTo(x)
		pathy = self.pathTo(y)
		i = 0
		while i < len(pathx) and i < len(pathy) and (pathx[i] == pathy[i]):
			i += 1
		return len(pathx) + len(pathy) - 2 * i


class Solution:

	def shortestPath(self, x, y):
		path_x = []
		x_len = 0
		while x:
			path_x.append(x)
			x //= 2
			x_len += 1
		path_y = []
		y_len = 0
		while y:
			path_y.append(y)
			y //= 2
			y_len += 1
		(i, j) = (x_len - 1, y_len - 1)
		while i >= 0 and j >= 0 and (path_x[i] == path_y[j]):
			i -= 1
			j -= 1
		return i + 1 + j + 1


import heapq

class Solution:

	def shortestPath(self, x, y):
		a = [1]
		c = 0
		while x > 0 and y > 0:
			if x > y:
				x = x // 2
			elif y > x:
				y = y // 2
			else:
				return c
			c += 1
		d = -1
		while y > 0:
			y = y // 2
			d += 1
		return c + d


class Solution:

	def shortestPath(self, x, y):
		dist = 0
		while x != y:
			if x > y:
				x = int(x >> 1)
			else:
				y = int(y >> 1)
			dist += 1
		return dist
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(x, y) = map(int, input().strip().split())
		ob = Solution()
		print(ob.shortestPath(x, y))


class Solution:

	def shortestPath(self, x, y):
		(a, b) = (bin(max(x, y))[2:], bin(min(x, y))[2:])
		ans = len(a) - len(b)
		a = a[:len(b)]
		while a != b:
			ans += 2
			(a, b) = (a[:-1], b[:-1])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(x, y) = map(int, input().strip().split())
		ob = Solution()
		print(ob.shortestPath(x, y))


class Solution:

	def shortestPath(self, x, y):
		count = 1
		a = 0
		b = 0
		while x >= 1 and y >= 1:
			a = max(x, y)
			b = min(x, y)
			if a // 2 == b:
				return count
			else:
				count += 1
				x = a // 2
				y = b
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(x, y) = map(int, input().strip().split())
		ob = Solution()
		print(ob.shortestPath(x, y))


class Solution:

	def shortestPath(self, x, y, ct=0):
		if x == y:
			return ct
		elif x > y:
			return self.shortestPath(x // 2, y, ct + 1)
		elif x < y:
			return self.shortestPath(x, y // 2, ct + 1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(x, y) = map(int, input().strip().split())
		ob = Solution()
		print(ob.shortestPath(x, y))


from math import log, ceil, floor

class Solution:

	def shortestPath(self, x, y):
		dist = 0
		while x != y:
			if x > y:
				x = x >> 1
			else:
				y = y >> 1
			dist += 1
		return dist


class Solution:

	def shortestPath(self, x, y):
		res = 0
		while True:
			if x == y:
				break
			elif x > y:
				x //= 2
				res += 1
			else:
				y //= 2
				res += 1
		return res


class Solution:

	def shortestPath(self, x, y):
		x_ = 0
		while x != y:
			if x > 1 and x > y:
				if (x - 1) % 2 != 0:
					x = x // 2
				else:
					x = (x - 1) // 2
				x_ += 1
			elif y > 1 and y > x:
				if (y - 1) % 2 != 0:
					y = y // 2
				else:
					y = (y - 1) // 2
				x_ += 1
		return x_


class Solution:

	def shortestPath(self, x, y):
		ans = 0
		if x > y:
			(x, y) = (y, x)
		while x != y:
			y //= 2
			ans += 1
			if y < x:
				x //= 2
				ans += 1
		return ans


class Solution:

	def shortestPath(self, x, y):
		count = 0
		xmin = min(x, y)
		xmax = max(x, y)
		x = xmin
		y = xmax
		while x != y:
			while x < y:
				y = y // 2
				count += 1
			xmin = min(x, y)
			xmax = max(x, y)
			x = xmin
			y = xmax
		return count


class Solution:

	def shortestPath(self, x, y):
		first = []
		while x != 1:
			first.append(x)
			x //= 2
		first = first[::-1]
		second = []
		while y != 1:
			second.append(y)
			y //= 2
		second = second[::-1]
		while first and second and (first[0] == second[0]):
			first.pop(0)
			second.pop(0)
		return len(first) + len(second)


from collections import deque

class Node:

	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None

class Solution:

	def shortestPath(self, x, y):
		res = 0
		a = max(x, y)
		b = min(x, y)
		while a != b:
			while a != b and a > b:
				a = a // 2
				res += 1
			(a, b) = (b, a)
		return res


class Solution:

	def shortestPath(self, x, y):
		(a, b) = (bin(x)[2:], bin(y)[2:])
		c_len = 0
		for i in range(min(len(a), len(b))):
			if a[i] != b[i]:
				break
			c_len += 1
		return len(a) + len(b) - 2 * c_len


class Solution:

	def shortestPath(self, x, y):
		next_node = 0
		path = 0
		x_path = [x]
		y_path = [y]
		while x > 1:
			if x % 2 == 0:
				x = int(x / 2)
			else:
				x = int((x - 1) / 2)
			x_path.append(x)
		while y > 1:
			if y % 2 == 0:
				y = int(y / 2)
			else:
				y = int((y - 1) / 2)
			y_path.append(y)
		for i in range(len(x_path)):
			if x_path[i] in y_path:
				path = i + y_path.index(x_path[i])
				break
		return path


def f(x, y):
	if x == y:
		return x
	if x < y:
		return f(x, y // 2)
	return f(x // 2, y)

def l(r, x):
	if r == x:
		return 0
	return 1 + l(r, x // 2)

class Solution:

	def shortestPath(self, x, y):
		t = f(x, y)
		return l(t, x) + l(t, y)


class Solution:

	def shortestPath(self, origin, destination):
		pathLength = 0
		originIntermediate = origin
		destinationIntermediate = destination
		while originIntermediate != destinationIntermediate:
			if originIntermediate > destinationIntermediate:
				originIntermediate = originIntermediate // 2
			else:
				destinationIntermediate = destinationIntermediate // 2
			pathLength += 1
		return pathLength


class Solution:

	def shortestPathHelper(self, x, y):
		distance = 0
		while x != y:
			if x > y:
				x //= 2
			else:
				y //= 2
			distance += 1
		return distance

	def shortestPath(self, x, y):
		return self.shortestPathHelper(x, y)


class Solution:

	def shortestPath(self, x, y):
		(l1, l2) = ([], [])
		(n, m) = (0, 0)
		while x > 0:
			l1.append(x)
			x = x // 2
			n += 1
		while y > 0:
			l2.append(y)
			y = y // 2
			m += 1
		i = j = 0
		while i < n and j < m:
			if l1[i] == l2[j]:
				return i + j
			elif l1[i] > l2[j]:
				i += 1
			else:
				j += 1


class Solution:

	def shortestPath(self, x, y):
		c = 0
		while 1:
			if x > y:
				x = x // 2
				c += 1
			elif y > x:
				y = y // 2
				c += 1
			else:
				return c


import collections

class Solution:

	def pathFinder(self, num):
		q = collections.deque()
		q.append([num, 0])
		ans = 0
		while q:
			(val, count) = q.popleft()
			new_val = val // 2
			if new_val in self.visited:
				return [True, self.visited[new_val] + count + 1]
			if new_val == 1:
				ans += count + 1
			elif new_val == x:
				return [True, count + 1]
			elif new_val > 1:
				self.visited[new_val] = count + 1
				q.append([new_val, count + 1])
		return [False, ans]

	def shortestPath(self, x, y):
		if x == y:
			return 0
		if 2 * x == y or x == 2 * y:
			return 1
		self.visited = {}
		if x > y:
			ans = self.pathFinder(x)
		else:
			ans = self.pathFinder(y)
		if ans[0]:
			return ans[1]
		if x > y:
			if y in self.visited:
				return self.visited[y]
			temp = self.pathFinder(y)
		else:
			if x in self.visited:
				return self.visited[x]
			temp = self.pathFinder(x)
		if temp[0]:
			return temp[1]
		return ans[1] + temp[1]


import math

class Solution:

	def shortestPath(self, x, y):
		path = 0
		if x == y:
			return path
		while x != y:
			if x > y:
				x = math.floor(x / 2)
			else:
				y = math.floor(y / 2)
			path = path + 1
		return path


class Solution:

	def shortestPath(self, x, y):
		length = 0
		while x != y:
			if x > y:
				x = int(x / 2)
			else:
				y = int(y / 2)
			length = length + 1
		return length


class Solution:

	def shortestPath(self, x, y):
		if x == y:
			return 0
		a = {}
		b = {}
		a[x] = 0
		b[y] = 0
		c = 1
		while x > 0:
			x //= 2
			a[x] = c
			c += 1
		c = 1
		while y > 0:
			y //= 2
			b[y] = c
			c += 1
		ans = -1
		for i in a:
			if i in b:
				if ans == -1:
					ans = a[i] + b[i]
				else:
					ans = min(ans, a[i] + b[i])
		return ans


class Solution:

	def shortestPath(self, x, y):
		if x == y:
			return 0
		xcnt = ycnt = 0
		while x != y:
			if x < y:
				y = y // 2
				ycnt += 1
			else:
				x = x // 2
				xcnt += 1
		return xcnt + ycnt


import math

class Solution:

	def shortestPath(self, x, y):
		l_x = int(math.log2(x))
		l_y = int(math.log2(y))
		while x != y:
			if x > y:
				x = x // 2
			elif x < y:
				y = y // 2
		l_z = int(math.log2(x))
		res = l_x + l_y - 2 * l_z
		return res


class Solution:
	path = 0

	def shortestPath(self, x, y):
		mx = max(x, y)
		mn = min(x, y)
		p = 0
		while mx != mn:
			if mx > mn:
				mx = mx // 2
				p = p + 1
			if mx < mn:
				mn = mn // 2
				p = p + 1
		return p