Given a rectangle of some length and width, How do you divide them into minimum number of squares? This is a problem from Codechef.
For example give a rectangle of size 2 x 4, we can make them into two squares of 2 x 2.
Similarly a rectangle of size 3 x 7, can only be divided into 21 squares each of size 1 x 1.
So what is the logic behind this?
The length and width should be divided in same equal parts, and that part should as greater as possible. So we have to find the GCD(Greatest Common Divisor) of the length and width of the rectangle. Then the minimum number of squares can be calculated by
l/g * w/g. where l = length, w = width, g = GCD(l,w)
Here is the C++ code which implements this.
For example give a rectangle of size 2 x 4, we can make them into two squares of 2 x 2.
Similarly a rectangle of size 3 x 7, can only be divided into 21 squares each of size 1 x 1.
So what is the logic behind this?
The length and width should be divided in same equal parts, and that part should as greater as possible. So we have to find the GCD(Greatest Common Divisor) of the length and width of the rectangle. Then the minimum number of squares can be calculated by
l/g * w/g. where l = length, w = width, g = GCD(l,w)
Here is the C++ code which implements this.