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\):


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 “softskills 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:


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

