Given a rectangle of size L x B. Find the minimum number of squares required to fill the rectangle such that no two square overlaps.
Example 1:
Input: L = 4, B = 5
Output: 5
Explaination: One 4*4 square and four 1*1 
squares are required.
Example 2:
Input: L = 2, B = 4
Output: 2
Explaintion: Two 2*2 squares are enough to 
fill the rectangle.
Your Task:
You do not need to read input or print anything. Your task is to complete the  function minSquares() which takes L and B as input parameters and returns minimum number of squares required to fill the rectangle. Return the answer modulo 10^{9} + 7.
Expected Time Complexity: O(log(max(L, B)))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ L, B ≤ 10^{10}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def minSquares(self, L, B):
        # code here

Solutions:
class Solution:

	def minSquares(self, L, B):
		p = 1000000007
		if L == 1:
			return B % p
		if B == 1:
			return L % p
		ans = 0
		while L > 0 and B > 0:
			if L > B:
				ans = (ans + L // B) % p
				L = L % B
			else:
				ans = (ans + B // L) % p
				B = B % L
		return ans % p


class Solution:

	def minSquares(self, l, b):
		p = 1000000007
		if l == 1:
			return b % p
		if b == 1:
			return l % p
		ans = 0
		while l > 0 and b > 0:
			if l > b:
				ans = (ans + l // b) % p
				l = l % b
			else:
				ans = (ans + b // l) % p
				b = b % l
		return ans % p


import math

class Solution:

	def minSquares(self, L, B):
		if L > B:
			(L, B) = (B, L)
		res = 0
		while L:
			res += B // L
			B %= L
			if L > B:
				(B, L) = (L, B)
		return res % 1000000007


class Solution:

	def minSquares(self, L, B):
		cnt = 0
		while True:
			if L == B or L <= 0 or B <= 0:
				if L == 0 or B == 0:
					break
				else:
					cnt += 1
					break
			elif L < B:
				temp = B // L
				cnt += temp
				B -= L * temp
			else:
				temp = L // B
				cnt += temp
				L -= B * temp
		return cnt % (10 ** 9 + 7)


class Solution:

	def minSquares(self, L, B):
		if L > B:
			L = L + B
			B = L - B
			L = L - B
		if B % L == 0:
			return B // L % 1000000007
		else:
			r = B % L
			sum = B // L
			while r != 0:
				sum += L // r
				B = L
				L = r
				r = B % L
			return sum % 1000000007


class Solution:

	def minSquares(self, L, B):
		count = 0
		while L >= 0 or B >= 0:
			if L == 0 or B == 0:
				return count % (10 ** 9 + 7)
			if L == 1:
				count += B
				return count % (10 ** 9 + 7)
			if B == 1:
				count += L
				return count % (10 ** 9 + 7)
			if L > B and B != 0:
				x = L // B
				L -= B * x
				count += x
			if B >= L and L != 0:
				y = B // L
				B -= L * y
				count += y


class Solution:

	def solve(self, L, B):
		mod = 10 ** 9 + 7
		if L == B:
			return 1
		if B == 0 or L == 0:
			return 0
		if L == 1 or B == 1:
			return max(L, B)
		if L > B:
			return self.solve(B, L)
		return B // L + self.solve(L, B % L) % mod

	def minSquares(self, L, B):
		mod = 10 ** 9 + 7
		return int(self.solve(L, B)) % mod


class Solution:

	def minSquares(self, l, b):
		mod = pow(10, 9) + 7

		def solve(l, b):
			if l == 0 or b == 0:
				return 0
			if l >= b:
				return l // b + solve(l % b, b)
			if l < b:
				return b // l + solve(l, b % l)
		return solve(l, b) % mod