# Hackerrank Solution: Restaurant

Original Problem

Martha is interviewing at Subway. One of the rounds of the interview requires her to cut a bread of size $$l\times b$$ into smaller identical pieces such that each piece is a square having maximum possible side length with no left over piece of bread.

Input Format

The first line contains an integer $$T$$.$$T$$ lines follow. Each line contains two space separated integers $$l$$ and $$b$$ which denote length and breadth of the bread.

Constraints

$$1\leq T\leq 1000$$

$$1\leq l, b\leq 1000$$

Output Format

$$T$$ lines, each containing an integer that denotes the number of squares of maximum size, when the bread is cut as per the given condition.

Sample Input

2
2 2
6 9


Sample Output

1
6


Explanation

The 1st testcase has a bread whose original dimensions are $$2\times 2$$, the bread is uncut and is a square. Hence the answer is 1.
The 2nd testcase has a bread of size $$6\times 9$$. We can cut it into 54 squares of size $$1\times 1$$, 6 of size $$3\times 3$$. For other sizes we will have leftovers. Hence, the number of squares of maximum size that can be cut is 6.

## Solution

The question asks on how large can a square piece be to fit into the original area without any remainder. When we take another example with a bread of size $$10\times 15$$ it is clear that to be square the largest common factor we can find is 5 such that we can order $$2\times 3$$ squares of size 5. This is everything needed to solve the problem:

$\begin{array}{rl} R(l, b) =& \frac{l}{\gcd(l, b)}\cdot\frac{b}{\gcd(l, b)}\\ =& \frac{l\cdot b}{\gcd(l, b)^2} \end{array}$

The function can be implemented straight ahead with Ruby:

def restaurant(l, b)
l * b / l.gcd(b)**2
end

« Back to problem overview