There is a carpet of a size a*b [length * breadth]. You are given a box of size c*d. The task is, one has to fit the carpet in the box in a minimum number of moves. 
In one move, you can either decrease the length or the breadth of the carpet by half (floor value of its half).
Note: One can even turn the carpet by 90 degrees any number of times, wont be counted as a move.
 
Example 1:
Input:
A = 8, B = 13
C = 6, D = 10
Output:
Minimum number of moves: 1
Explanation:
Fold the carpet by breadth, 13/2 i.e. 6, 
so now carpet is 6*8 and can fit fine.
 
Example 2:
Input:
A = 4, B = 8
C = 3, D = 10
Output:
Minimum number of moves: 1
Explanation: Fold the carpet by length , 4/2 i.e. 2,
so now carpet is 2*8 and can fit fine.
 
Your Task:
You don't need to read input or print anything. You only need to complete the function carpetBox() that takes an integer A, B, C and D as input and returns an integer denoting the minimum numbers of moves required to fit the carpet into the box.
 
Expected Time Complexity: O( max( log(a), log(b) ) ) .
Expected Auxiliary Space: O(1) .
 
Constrains:
1<= A,B,C,D <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3





class Solution:

    def carpetBox(self, A,B,C,D):

        #code here



Solutions:
class Solution:

	def carpetBox(self, A, B, C, D):
		count = 0
		max_cd = max(C, D)
		min_cd = min(C, D)
		max_ab = max(A, B)
		min_ab = min(A, B)
		while max_ab > max_cd or min_ab > min_cd:
			if max_ab > max_cd and max_ab == A:
				A //= 2
			elif max_ab > max_cd and max_ab == B:
				B //= 2
			elif min_ab > min_cd and min_ab == A:
				A //= 2
			elif min_ab > min_cd and min_ab == B:
				B //= 2
			count += 1
			max_ab = max(A, B)
			min_ab = min(A, B)
		return count


class Solution:

	def carpetBox(self, A, B, C, D):
		if B > A:
			(A, B) = (B, A)
		if C < D:
			(C, D) = (D, C)
		moves = 0
		while A > C:
			A //= 2
			moves += 1
		while B > C:
			B //= 2
			moves += 1
		if A < B:
			(A, B) = (B, A)
		while B > D:
			B //= 2
			moves += 1
		return moves


class Solution:

	def carpetBox(self, A, B, C, D):
		m1 = 0
		(Ao, Bo) = (A, B)
		while A > C or B > D:
			if A > C:
				A //= 2
			else:
				B //= 2
			m1 += 1
		(A, B) = (Bo, Ao)
		m2 = 0
		while A > C or B > D:
			if A > C:
				A //= 2
			else:
				B //= 2
			m2 += 1
		return min(m1, m2)


class Solution:

	def carpetBox(self, A, B, C, D):
		val1 = val2 = 0
		(E, F, G, H) = (A, B, C, D)
		while A > C or B > D:
			if A > C:
				A //= 2
			else:
				B //= 2
			val1 += 1
		while E > H or F > G:
			if E > H:
				E //= 2
			else:
				F //= 2
			val2 += 1
		return min(val1, val2)


class Solution:

	def carpetBox(self, A, B, C, D):
		d = dict()

		def dfs(a, b):
			if a == 0 or b == 0:
				return 10 ** 18
			if a <= C and b <= D or (a <= D and b <= C):
				return 0
			if d.get((a, b)) != None:
				return d[a, b]
			d[a, b] = min(1 + dfs(a // 2, b), 1 + dfs(a, b // 2))
			return d[a, b]
		return dfs(A, B)


class Solution:

	def carpetBox(self, A, B, C, D):
		dp = {}
		length = A
		breadth = B
		non_rotated = 0
		while length > C or breadth > D:
			if length > C:
				non_rotated += 1
				length = length // 2
			if breadth > D:
				non_rotated += 1
				breadth = breadth // 2
		length = B
		breadth = A
		rotated = 0
		while length > C or breadth > D:
			if length > C:
				rotated += 1
				length = length // 2
			if breadth > D:
				rotated += 1
				breadth = breadth // 2
		return min(rotated, non_rotated)


class Solution:

	def carpetBox(self, A, B, C, D):
		dp = dict()
		return self.solve(A, B, C, D, dp)

	def solve(self, a, b, c, d, dp):
		if (a, b) in dp:
			return dp[a, b]
		if max(a, b) <= max(c, d) and min(a, b) <= min(c, d):
			return 0
		x = 10 ** 9
		y = 10 ** 9
		z = 10 ** 9
		if min(a, b) < max(c, d):
			if a <= c or a <= d:
				x = self.solve(a, b // 2, c, d, dp) + 1
			if b <= c or b <= d:
				y = self.solve(a // 2, b, c, d, dp) + 1
		else:
			z = min(self.solve(a // 2, b, c, d, dp), self.solve(a, b // 2, c, d, dp)) + 1
		dp[a, b] = min(x, y, z)
		return dp[a, b]


class Solution:

	def carpetBox(self, A, B, C, D):
		x = max(A, B)
		y = min(A, B)
		count = 0
		l = max(C, D)
		w = min(C, D)
		while x > l:
			x = x // 2
			count += 1
			if x < l and y > w:
				if x < y:
					z = x + y
					x = z - x
					y = z - y
		while y > w:
			y = y // 2
			count += 1
		return count


class Solution:

	def carpetBox(self, A, B, C, D):
		(x, y, s) = (A, B, 0)
		while x > C or y > D:
			if x > C:
				x = int(x / 2)
				s += 1
			if y > D:
				y = int(y / 2)
				s += 1
		ans = s
		(x, y, s) = (A, B, 0)
		while x > D or y > C:
			if x > D:
				x = int(x / 2)
				s += 1
			if y > C:
				y = int(y / 2)
				s += 1
		return min(ans, s)


class Solution:

	def carpetBox(self, A, B, C, D):
		if C > D:
			temp = C
			C = D
			D = temp

		def fun(a, b):
			if (a, b) in dic:
				return dic[a, b]
			if min(a, b) <= C and max(a, b) <= D:
				return 0
			temp = float('inf')
			if a > C or a > D:
				temp = min(temp, fun(a // 2, b))
			if b > C or b > D:
				temp = min(temp, fun(a, b // 2))
			dic[a, b] = 1 + temp
			return 1 + temp
		dic = {}
		return fun(A, B)


class Solution:

	def carpetBox(self, A, B, C, D):
		x = A
		y = B
		count = 0
		count2 = 0
		while x > C or y > D:
			if x > C:
				x = x // 2
				count += 1
			if y > D:
				y = y // 2
				count += 1
		x = A
		y = B
		while x > D or y > C:
			if x > D:
				x = x // 2
				count2 += 1
			if y > C:
				y = y // 2
				count2 += 1
		return min(count, count2)


class Solution:

	def carpetBox(self, A, B, C, D):
		box = C * D
		carpet = A * B
		carpeta = A * B
		carpetb = A * B
		length = A
		breadth = B
		moves1 = 0
		moves = 0
		prevl = length
		prevb = breadth
		while length > C or breadth > D:
			if length > C:
				moves += 1
				length //= 2
			if breadth > D:
				moves += 1
				breadth //= 2
		length = prevb
		breadth = prevl
		while length > C or breadth > D:
			if length > C:
				moves1 += 1
				length //= 2
			if breadth > D:
				moves1 += 1
				breadth //= 2
		return min(moves, moves1)


class Solution:

	def carpetBox(self, A, B, C, D):
		if A >= max(C, D) and B >= max(C, D):
			ans = 0
			while max(A, B) > max(C, D):
				if A > B:
					A = A // 2
					ans += 1
				else:
					B = B // 2
					ans += 1
			if min(A, B) <= min(C, D):
				if A > B:
					while A > max(C, D):
						A = A // 2
						ans += 1
					return ans
				else:
					while B > max(C, D):
						B = B // 2
						ans += 1
					return ans
			elif A < B:
				while A > min(C, D):
					A = A // 2
					ans += 1
				return ans
			else:
				while B > min(C, D):
					B = B // 2
					ans += 1
				return ans
		elif A >= max(C, D) or B >= max(C, D):
			ans = 0
			if min(A, B) <= min(C, D):
				if A > B:
					while A > max(C, D):
						A = A // 2
						ans += 1
					return ans
				else:
					while B > max(C, D):
						B = B // 2
						ans += 1
					return ans
			elif A < B:
				while A > min(C, D):
					A = A // 2
					ans += 1
				return ans
			else:
				while B > min(C, D):
					B = B // 2
					ans += 1
				return ans
		elif A <= min(C, D) or B <= min(C, D):
			return 0
		else:
			ans = 0
			if A < B:
				while A > min(C, D):
					A = A // 2
					ans += 1
				return ans
			else:
				while B > min(C, D):
					B = B // 2
					ans += 1
				return ans


class Solution:

	def carpetBox(self, A, B, C, D):

		def help(a, b):
			ans = 0
			while a > C:
				ans += 1
				a >>= 1
			while b > D:
				ans += 1
				b >>= 1
			return ans
		return min(help(A, B), help(B, A))


class Solution:

	def carpetBox(self, A, B, C, D):
		(a, b) = (min(A, B), max(A, B))
		(c, d) = (min(C, D), max(C, D))
		if a <= c and b <= d:
			return 0
		if b > d:
			return 1 + self.carpetBox(a, b // 2, c, d)
		return 1 + self.carpetBox(a // 2, b, c, d)


class Solution:

	def carpetBox(self, A, B, C, D):
		x = 0
		while 1:
			if max(A, B) > max(C, D):
				if A > B:
					A //= 2
				else:
					B //= 2
			elif min(A, B) > min(C, D):
				if A < B:
					A //= 2
				else:
					B //= 2
			else:
				break
			x += 1
		return x


class Solution:

	def carpetBox(self, a, b, c, d):
		l1 = []
		l2 = []
		while a != 0:
			l1.append(a)
			a = a // 2
		while b != 0:
			l2.append(b)
			b = b // 2
		ans = float('inf')
		for i in range(len(l1)):
			for j in range(len(l2)):
				if l1[i] <= c and l2[j] <= d or (l2[j] <= c and l1[i] <= d):
					ans = min(ans, i + j)
		return ans


class Solution:

	def carpetBox(self, A, B, C, D):
		X = max(A, B)
		Y = min(A, B)
		count = 0
		L = max(C, D)
		W = min(C, D)
		while X > L:
			X = X // 2
			count += 1
			if X < L and Y > W:
				if X < Y:
					Z = X + Y
					X = Z - X
					Y = Z - Y
		while Y > W:
			Y = Y // 2
			count += 1
		return count


class Solution:

	def carpetBox(self, A, B, C, D):
		count = 0
		while max(A, B) > max(C, D):
			if A >= B:
				A = A // 2
			else:
				B = B // 2
			count += 1
		while min(A, B) > min(C, D):
			if A <= B:
				A = A // 2
			else:
				B = B // 2
			count += 1
		return count


import math

class Solution:

	def carpetBox(self, A, B, C, D):
		MaxC = max(A, B)
		MinC = min(A, B)
		MaxB = max(C, D)
		MinB = min(C, D)
		ans = 0
		if MinC <= MinB and MaxC <= MaxB:
			return ans
		while MaxC > MaxB:
			MaxC = math.floor(MaxC // 2)
			temp = MaxC
			MaxC = max(MaxC, MinC)
			MinC = min(MinC, temp)
			ans += 1
		while MinC > MinB:
			MinC = math.floor(MinC // 2)
			temp = MinC
			MinC = min(MaxC, MinC)
			MaxC = max(MaxC, temp)
			ans += 1
		return ans


def maxer(num1, num2):
	if num1 > num2:
		return num1
	else:
		return num2

def minner(num1, num2):
	if num1 < num2:
		return num1
	else:
		return num2

class Solution:

	def carpetBox(self, A, B, C, D):
		count = 0
		max_cd = maxer(C, D)
		min_cd = minner(C, D)
		max_ab = maxer(A, B)
		min_ab = minner(A, B)
		while max_ab > max_cd or min_ab > min_cd:
			if max_ab > max_cd and max_ab == A:
				A //= 2
			elif max_ab > max_cd and max_ab == B:
				B //= 2
			elif min_ab > min_cd and min_ab == A:
				A //= 2
			elif min_ab > min_cd and min_ab == B:
				B //= 2
			count += 1
			max_ab = maxer(A, B)
			min_ab = minner(A, B)
		return count


class Solution:

	def carpetBox(self, A, B, C, D):
		length1 = A
		breadth1 = B
		moves_without_rotation = 0
		moves_with_rotation = 0
		while A > C:
			A = A // 2
			moves_without_rotation += 1
		while B > D:
			B = B // 2
			moves_without_rotation += 1
		length2 = breadth1
		breadth2 = length1
		while length2 > C:
			length2 = length2 // 2
			moves_with_rotation += 1
		while breadth2 > D:
			breadth2 = breadth2 // 2
			moves_with_rotation += 1
		return min(moves_without_rotation, moves_with_rotation)


class Solution:

	def carpetBox(self, A, B, C, D):
		if A <= C and B <= D or (B <= C and A <= D):
			return 0
		if A > C and A > D:
			return 1 + self.carpetBox(A // 2, B, C, D)
		if B > C and B > D:
			return 1 + self.carpetBox(A, B // 2, C, D)
		return min(1 + self.carpetBox(A // 2, B, C, D), 1 + self.carpetBox(A, B // 2, C, D))


from math import log2, ceil

class Solution:

	def carpetBox(self, c, d, a, b):

		def times(i, j):
			t = 0
			while i > j:
				i //= 2
				t += 1
			return t
		return min(times(c, a) + times(d, b), times(c, b) + times(d, a))


class Solution:

	def carpetBox(self, A, B, C, D):
		moves = 0
		while not (A <= C and B <= D or (A <= D and B <= C)):
			if A > C and A > D:
				A = A // 2
				moves += 1
			if B > C and B > D:
				B = B // 2
				moves += 1
			if A > C and B > C and (A <= D) and (B <= D):
				if A - C < B - C:
					A = A // 2
				else:
					B = B // 2
				moves += 1
			elif A > D and B > D and (A <= C) and (B <= C):
				if A - D < B - D:
					A = A // 2
				else:
					B = B // 2
				moves += 1
		return moves


class Solution:

	def carpetBox(self, A, B, C, D):
		count1 = 0
		count2 = 0
		temp_1 = A
		temp_2 = B
		while A > C:
			A = A // 2
			count1 += 1
		while B > D:
			B = B // 2
			count1 += 1
		A = temp_2
		B = temp_1
		while A > C:
			A = A // 2
			count2 += 1
		while B > D:
			B = B // 2
			count2 += 1
		return min(count1, count2)


class Solution:

	def carpetBox(self, A, B, C, D):
		cnt = 0
		l1 = max(A, B)
		l2 = max(C, D)
		b1 = min(A, B)
		b2 = min(C, D)
		while l1 > l2:
			cnt += 1
			l1 //= 2
			if l1 <= b1:
				(l1, b1) = (b1, l1)
		while b1 > b2:
			cnt += 1
			b1 //= 2
		return cnt


class Solution:

	def carpetBox(self, A, B, C, D):
		carpet = [A, B]
		carpet.sort()
		box = [C, D]
		box.sort()
		moves = 0
		while True:
			if carpet[0] <= box[0] and carpet[1] <= box[1]:
				return moves
			if carpet[0] > box[0] and carpet[1] > box[1]:
				if carpet[1] > carpet[0]:
					carpet[1] //= 2
					carpet.sort()
				else:
					carpet[0] //= 2
			elif carpet[0] > box[0]:
				carpet[0] //= 2
			elif carpet[0] <= box[1]:
				carpet[1] //= 2
				carpet.sort()
			else:
				carpet[0] //= 2
			moves += 1


def get_count(A, B, C, D):
	a = A
	b = B
	count = 0
	while a > C:
		count += 1
		a = a // 2
	while b > D:
		count += 1
		b = b // 2
	return count

class Solution:

	def carpetBox(self, A, B, C, D):
		normal_count = get_count(A, B, C, D)
		flippped_count = get_count(A, B, D, C)
		return min(normal_count, flippped_count)


from collections import deque

class Solution:

	def carpetBox(self, A, B, C, D):
		queue = deque([(A, B, 0)])
		visited = set()
		while queue:
			(a, b, moves) = queue.popleft()
			if (a, b) in visited:
				continue
			visited.add((a, b))
			if a <= C and b <= D or (a <= D and b <= C):
				return moves
			queue.append((a // 2, b, moves + 1))
			queue.append((a, b // 2, moves + 1))
		return -1


class Solution:

	def carpetBox(self, A, B, C, D):
		fold_r = 0
		fold_wr = 0
		A_r = A
		B_r = B
		while A_r > C:
			A_r = A_r // 2
			fold_r += 1
		while B_r > D:
			B_r = B_r // 2
			fold_r += 1
		while A > D:
			A = A // 2
			fold_wr += 1
		while B > C:
			B = B // 2
			fold_wr += 1
		return min(fold_r, fold_wr)


class Solution:

	def carpetBox(self, a, b, c, d):
		(a, b) = (min(a, b), max(a, b))
		(c, d) = (min(c, d), max(c, d))
		if a <= c and b <= d or (a <= d and b <= c):
			return 0
		if a > c and b <= d:
			return 1 + self.carpetBox(a // 2, b, c, d)
		else:
			return 1 + self.carpetBox(a, b // 2, c, d)


def solve(a, b, c, d):
	len_car = max(a, b)
	bred_car = min(a, b)
	if len_car > c:
		return 1 + solve(len_car // 2, bred_car, c, d)
	elif bred_car > d:
		return 1 + solve(len_car, bred_car // 2, c, d)
	else:
		return 0

class Solution:

	def carpetBox(self, A, B, C, D):
		(a, b, c, d) = (A, B, C, D)
		(l_box, b_box) = (max(c, d), min(c, d))
		res = solve(a, b, l_box, b_box)
		return res


class Solution:

	def carpetBox(self, A, B, C, D):
		maxi = max(A, B)
		mini = min(A, B)
		moves = 0
		while maxi > max(C, D):
			maxi //= 2
			if maxi <= mini:
				(maxi, mini) = (mini, maxi)
			moves += 1
		while mini > min(C, D):
			mini //= 2
			moves += 1
		return moves


class Solution:

	def carpetBox(self, A, B, C, D):
		c_length = max(A, B)
		c_breadth = min(A, B)
		b_length = max(C, D)
		b_breadth = min(C, D)
		ans = 0
		while c_length > b_length or c_breadth > b_breadth:
			if c_length > b_length and c_breadth > b_breadth:
				c_length //= 2
			elif c_length > b_length:
				c_length //= 2
			else:
				c_breadth //= 2
			A = c_length
			B = c_breadth
			c_length = max(A, B)
			c_breadth = min(A, B)
			ans += 1
		return ans


def solve(a, b, c, d):
	q = max(a, b)
	w = max(c, d)
	e = min(a, b)
	r = min(c, d)
	if q > w:
		return 1 + solve(q // 2, e, c, d)
	elif e > r:
		return 1 + solve(q, e // 2, c, d)
	else:
		return 0

class Solution:

	def carpetBox(self, A, B, C, D):
		return solve(A, B, C, D)


class Solution:

	def carpetBox(self, A, B, C, D):
		moves_wo = 0
		moves_w = 0
		L1 = A
		B1 = B
		while A > C:
			A = A // 2
			moves_wo += 1
		while B > D:
			B = B // 2
			moves_wo += 1
		A = B1
		B = L1
		while A > C:
			A = A // 2
			moves_w += 1
		while B > D:
			B = B // 2
			moves_w += 1
		return min(moves_wo, moves_w)


class Solution:

	def carpetBox(self, A, B, C, D):
		a = max(A, B)
		b = min(A, B)
		m = 0
		while a > max(C, D):
			a //= 2
			if a <= b:
				(a, b) = (b, a)
			m += 1
		while b > min(C, D):
			b //= 2
			m += 1
		return m


class Solution:

	def carpetBox(self, A, B, C, D):

		def solve(a, b, c, d):
			res = 0
			while a > c:
				a //= 2
				res += 1
			while b > d:
				b //= 2
				res += 1
			return res
		return min(solve(A, B, C, D), solve(B, A, C, D))


class Solution:

	def carpetBox(self, A, B, C, D):
		(a, b, c, d) = (A, B, C, D)
		moves1 = 0
		while a > c or b > d:
			if a / c > b / d:
				a = int(a / 2)
			else:
				b = int(b / 2)
			moves1 += 1
		(a, b, c, d) = (A, B, C, D)
		moves2 = 0
		while a > d or b > c:
			if a / d > b / c:
				a = int(a / 2)
			else:
				b = int(b / 2)
			moves2 += 1
		return min(moves1, moves2)


class Solution:

	def carpetBox(self, A, B, C, D):
		normal_count = 0
		X = B
		Y = A
		while A > C or B > D:
			if A > C:
				normal_count += 1
				A = A // 2
			if B > D:
				normal_count += 1
				B = B // 2
		rotated_count = 0
		while X > C or Y > D:
			if X > C:
				rotated_count += 1
				X = X // 2
			if Y > D:
				rotated_count += 1
				Y = Y // 2
		return min(normal_count, rotated_count)


class Solution:

	def carpetBox(self, A, B, C, D):

		def count(A, B, C, D, n):
			a = min(A, B)
			b = max(A, B)
			c = min(C, D)
			d = max(C, D)
			if b > d:
				return count(a, b // 2, c, d, n + 1)
			elif a > c:
				return count(a // 2, b, c, d, n + 1)
			else:
				return n
		return count(A, B, C, D, 0)


class Solution:

	def carpetBox(self, A, B, C, D):
		X = A
		Y = B
		moves = 0
		while X > C or Y > D:
			if X > C:
				X = X // 2
				moves += 1
			if Y > D:
				Y = Y // 2
				moves += 1
		X = A
		Y = B
		count = 0
		while X > D or Y > C:
			if X > D:
				X = X // 2
				count += 1
			if Y > C:
				Y = Y // 2
				count += 1
		return min(moves, count)


import math

class Solution:

	def carpetBox(self, A, B, C, D):
		count = 0
		ans = 0
		a = A
		b = B
		while a > C or b > D:
			if a > C:
				a = math.floor(a / 2)
				count = count + 1
			elif b > D:
				b = math.floor(b / 2)
				count = count + 1
		a = A
		b = B
		while a > D or b > C:
			if a > D:
				a = math.floor(a / 2)
				ans += 1
			elif b > C:
				b = math.floor(b / 2)
				ans += 1
		return min(ans, count)


class Solution:

	def carpetBox(self, A, B, C, D):
		count = 0
		lst = [A, B]
		lst.sort()
		aim = [C, D]
		aim.sort()
		while lst[1] > aim[1]:
			lst[1] = lst[1] // 2
			lst.sort()
			count += 1
		while lst[0] > aim[0]:
			lst[0] = lst[0] // 2
			count += 1
		return count


class Solution:

	def carpetBox(self, A, B, C, D):
		if A <= C and B <= D or (B <= C and A <= D):
			return 0
		count1 = fold(A, B, C, D)
		count2 = fold(B, A, C, D)
		return min(count1, count2)

def fold(a, b, c, d):
	if a <= c and b <= d or (b <= c and a <= d):
		return 0
	if a <= c:
		return 1 + fold(a, b >> 1, c, d)
	else:
		return 1 + fold(a >> 1, b, c, d)


class Solution:

	def carpetBox(self, A, B, C, D):
		H = A
		P = B
		count = 0
		while True:
			if A <= C and B <= D:
				break
			else:
				if A > C:
					A = A // 2
				else:
					B = B // 2
				count += 1
		count1 = 0
		while True:
			if H <= D and P <= C:
				break
			else:
				if H > D:
					H = H // 2
				else:
					P = P // 2
				count1 += 1
		if count1 > count:
			return count
		else:
			return count1


class Solution:

	def carpetBox(self, a, b, c, d):
		m = 0
		w = 0
		(l1, l2) = (a, b)
		while a > c:
			a //= 2
			m += 1
		while b > d:
			b //= 2
			m += 1
		(a, b) = (l2, l1)
		while a > c:
			a //= 2
			w += 1
		while b > d:
			b //= 2
			w += 1
		return min(m, w)


class Solution:

	def carpetBox(self, A, B, C, D):
		(a, b) = (A, B)
		res1 = 0
		while a > C:
			a >>= 1
			res1 += 1
		while b > D:
			b >>= 1
			res1 += 1
		(a, b) = (A, B)
		res2 = 0
		while a > D:
			a >>= 1
			res2 += 1
		while b > C:
			b >>= 1
			res2 += 1
		return min(res1, res2)