Given a rectangle of sides m and n. Cut the rectangle into smaller identical pieces such that each piece is a square having maximum possible side length with no leftover part of the rectangle. Print number of such squares formed.
Examples:
Input: 9 6 Output: 6 Rectangle can be cut into squares of size 3. Input: 4 2 Output: 2 Rectangle can be cut into squares of size 2.
Approach: The task is to cut the rectangle in squares with the side of length s without pieces of the rectangle left over, so s must divide both m and n. Also, the side of the square should be maximum possible, therefore, s should be the greatest common divisor of m and n.
so, s = gcd(m, n).
To find the number of squares the rectangle is cut into, the task to be done is to divide the area of a rectangle with an area of the square of size s.
// Java code for calculating
// the number of squares
import java.io.*;
class GFG
{
// Recursive function to
// return gcd of a and b
static int __gcd( int a, int b)
{
// Everything divides 0
if (a == 0 || b == 0 )
return 0 ;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b - a);
}
// Function to find
// number of squares
static int NumberOfSquares( int x,
int y)
{
// Here in built c++
// gcd function is used
int s = __gcd(x, y);
int ans = (x * y) / (s * s);
return ans;
}
// Driver Code
public static void main (String[] args)
{
int m = 385 , n = 60 ;
// Call the function
// NumberOfSquares
System.out.println(NumberOfSquares(m, n));
}
}
Output:
924