Given a rectangular sheet of length l and width w. we need to divide this sheet into square sheets such that the number of square sheets should be as minimum as possible.
Examples:
Input :l= 4 w=6
Output :6
We can form squares with side of 1 unit, But the number of squares will be 24, this is not minimum. If we make square with side of 2, then we have 6 squares. and this is our required answer.
And also we can’t make square with side 3, if we select 3 as square side, then whole sheet can’t be converted into squares of equal length.
Optimal length of the side of a square is equal to GCD of two numbers
- Java
// Java program to find minimum number of
// squares to make a given rectangle.
class GFG{
static int __gcd( int a, int b) {
if (b== 0 ) return a;
return __gcd(b,a%b);
}
static int countRectangles( int l, int w)
{
// if we take gcd(l, w), this
// will be largest possible
// side for suare, hence minimum
// number of square.
int squareSide = __gcd(l, w);
// Number of squares.
return (l * w) / (squareSide * squareSide);
}
// Driver code
public static void main(String[] args)
{
int l = 4 , w = 6 ;
System.out.println(countRectangles(l, w));
}
}
Output:
6
Also in Cpp,
// CPP program to find minimum number of
// squares to make a given rectangle.
#include <bits/stdc++.h>
using namespace std;
int countRectangles( int l, int w)
{
// if we take gcd(l, w), this
// will be largest possible
// side for suare, hence minimum
// number of square.
int squareSide = __gcd(l, w);
// Number of squares.
return (l * w) / (squareSide * squareSide);
}
// Driver code
int main()
{
int l = 4, w = 6;
cout << countRectangles(l, w) << endl;
return 0;
}
Output:
6