Restaurant

See the original problem on HackerRank.

Solutions

We have to cut a rectangular bread having size \(l * b\) into squares of equal dimension such that no piece of original bread is left over.

So we have to make cuts only vertically or horizontally. Hence we can conclude that if the length of a side of the square is \(a\), both \(l\) and \(b\) has to be divisible by \(a\).

In addition, \(a\) has to be as large as possible.

Hence, the problem reduces to finding an integer whose value is maximum as well as divisible by both \(l\) and \(b\). That is, finding the greatest common divisor (gcd) of \(l\) and \(b\):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int main()
{
    int T; cin >> T;
    while (T--)
    {
        int l, b; cin >> l >> b;
        const auto _gcd = gcd(l, b);
        const auto ll = l/_gcd;
        const auto bb = b/_gcd;
        cout << (ll * bb) << endl;
    }
}

This problem is easy but it’s useful to approach the problem from a purely mathematical point of view. Sometimes we just forget some basic concepts like gdc.

Another related “soft-skills challenge” is how to explain the algorithm/approach without referring to the gcd and other mathematical concepts like prime factorization and modulo operations. Imagine you can only use the 4 fundamental operations.

Another interesting point is about implementing gcd or learning if our language already provides one implementation. For instance, since C++17 we have a standard gcd function in the header numeric.

An Haskell solution by alepez, using the gcd function provided by Haskell standard library:

1
2
3
4
5
6
7

main = interact $ ser . fmap compute . de
de = fmap ((\[x, y] -> (x, y)) . fmap read) . fmap words . drop 1 . lines
ser = unlines . fmap show

compute (l, b) = (l `quot` z) * (b `quot` z)
  where
    z = gcd l b

If gcd wasn’t available, we should have implemented it like this:

1
2

gcd x 0 = x
gcd x y = gcd y (x `rem` y)