Hackerrank - Restaurant Solution
1 min read

Hackerrank - Restaurant Solution

Hackerrank - Restaurant Solution

Martha is interviewing at Subway. One of the rounds of the interview requires her to cut a bread of size  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 .  lines follow. Each line contains two space separated integers  and  which denote length and breadth of the bread.


Output Format

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 0

2 2
6 9

Sample Output 0


Explanation 0

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

Solution in Python

import math

def best(x,y):
    prod = x*y
    for i in range(2,int(math.sqrt(prod))+1)[::-1]:
        if not x%i and not y%i:
            return x*y//i**2
        return prod
for _ in range(int(input())):
    x,y = list(map(int,input().split()))

Enjoying these posts? Subscribe for more

Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.