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.
Input :l=3 w=5
Output :15
Optimal length of the side of a square is equal to GCD of two numbers
C++
// 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 square, hence minimum // number of square. int squareSide = __gcd(l, w); // Number of squares. return (l * w) / (squareSide * squareSide);}// Driver codeint main(){ int l = 4, w = 6; cout << countRectangles(l, w) << endl; return 0;} |
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 square, hence minimum // number of square. int squareSide = __gcd(l, w); // Number of squares. return (l * w) / (squareSide * squareSide);}// Driver codepublic static void main(String[] args){ int l = 4, w = 6; System.out.println(countRectangles(l, w));}}// This code is contributed by mits |
Python3
# Python3 code to find minimum number of# squares to make a given rectangle.import math def countRectangles(l, w): # if we take gcd(l, w), this # will be largest possible # side for square, hence minimum # number of square. squareSide = math.gcd(l,w) # Number of squares. return (l*w)/(squareSide*squareSide)# Driver Code if __name__ == '__main__': l = 4 w = 6 ans = countRectangles(l, w) print (int(ans))# this code is contributed by# SURENDRA_GANGWAR |
C#
// C# 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 square, hence minimum // number of square. int squareSide = __gcd(l, w); // Number of squares. return (l * w) / (squareSide * squareSide);}// Driver codepublic static void Main(){ int l = 4, w = 6; System.Console.WriteLine(countRectangles(l, w));}}// This code is contributed by mits |
PHP
<?php // PHP program to find minimum number // of squares to make a given rectangle.function gcd($a, $b){ return $b ? gcd($b, $a % $b) : $a;}function countRectangles($l, $w){ // if we take gcd(l, w), this // will be largest possible // side for square, hence minimum // number of square. $squareSide = gcd($l, $w); // Number of squares. return ($l * $w) / ($squareSide * $squareSide);}// Driver code$l = 4;$w = 6;echo countRectangles($l, $w) . "\n"; // This code is contributed // by ChitraNayal?> |
Javascript
<script>// Javascript program to find minimum number of// squares to make a given rectangle.function __gcd(a, b) { if (b==0) return a; return __gcd(b,a%b);}function countRectangles(l, w){ // if we take gcd(l, w), this // will be largest possible // side for square, hence minimum // number of square. let squareSide = __gcd(l, w); // Number of squares. return parseInt((l * w) / (squareSide * squareSide));}// Driver code let l = 4, w = 6; document.write(countRectangles(l, w));</script> |
Output:
6
Time Complexity: O(log(min(a, b))), where a and b are two parameters of gcd.
Auxiliary Space: O(log(min(a, b)))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
