See the original problem on HackerRank.
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\):
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
gcd function in the header
An Haskell solution by alepez, using the
gcd function provided by Haskell standard library:
gcd wasn’t available, we should have implemented it like this: