Given a rectangle of dimensions L x B find the minimum number (N) of identical squares of the maximum side that can be cut out from that rectangle so that no residue remains in the rectangle. Also, find the dimension K of that square.
Examples:
Input: L = 2, B = 4
Output: N = 2, K = 2
Explanation: 2 squares of 2×2 dimension.Input: L = 6, B = 3
Output: N = 2, K = 3
Explanation: 2 squares of 3×3 dimension.
Approach: To solve the problem follow the below idea:
In this method, we are using the GCD which is the greatest common divisor to compute the dimensions of the rectangle with the smallest possible area.
Follow the steps to solve the problem:
- Make a function with List return type name as minimumSquares which takes the length and breadth of the rectangle as input.
- Create an ArrayList of long types to store the minimum number of squares and the dimension of the square.
- Create two long variables and initialize them to 0.
- Find gcd (greatest common divisor) with the help of the gcd function and store it in K
- gcd function is a long return type that takes two long values as an input parameters.
- returns greatest common divisor
- Now as we have calculated the dimension of the required square and we know the area of the rectangle so just divide the area of the rectangle by the area of one square and we will get the number of squares.
- Now add values of N and K into ArrayList and return them.
Below is the implementation for the above approach:
C++
#include <iostream>
#include <vector>
using namespace std;
long long gcd(long long a, long long b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
vector<long long> minimumSquares(long long L, long long B) {
vector<long long> arr;
long long k = 0;
long long n = 0;
k = gcd(L, B);
n = (L * B) / (k * k);
arr.push_back(n);
arr.push_back(k);
return arr;
}
int main() {
long long L = 2, B = 4;
vector<long long> result = minimumSquares(L, B);
cout << result[0] << " " << result[1] << endl;
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
class GFG {
static long gcd(long a, long b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
static ArrayList<Long> minimumSquares(long L, long B)
{
// Code here
ArrayList<Long> arr = new ArrayList<>();
long k = 0;
long n = 0;
k = gcd(L, B);
n = (L * B) / (k * k);
arr.add(n);
arr.add(k);
return arr;
}
// Driver code
public static void main(String[] args)
{
int L = 2, B = 4;
System.out.println(minimumSquares(L, B));
}
}
Python3
# Python code for the above approach:
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
def minimumSquares(L, B):
arr = []
k = 0
n = 0
k = gcd(L, B)
n = (L * B) // (k * k)
arr.append(n)
arr.append(k)
return arr
# Driver code
L = 2
B = 4
result = minimumSquares(L, B)
print(result[0], result[1])
C#
// C# code for the above approach:
using System;
using System.Collections.Generic;
public class GFG {
static long gcd(long a, long b)
{
if (b == 0) {
return a;
}
else {
return gcd(b, a % b);
}
}
static List<long> minimumSquares(long L, long B)
{
List<long> arr = new List<long>();
long k = 0;
long n = 0;
k = gcd(L, B);
n = (L * B) / (k * k);
arr.Add(n);
arr.Add(k);
return arr;
}
static public void Main()
{
// Code
int L = 2, B = 4;
Console.Write("[");
Console.Write(
string.Join(", ", minimumSquares(L, B)));
Console.Write("]");
}
}
Javascript
function gcd(a, b) {
if (b === 0) {
return a;
} else {
return gcd(b, a % b);
}
}
function minimumSquares(L, B) {
const arr = [];
let k = 0;
let n = 0;
k = gcd(L, B);
n = (L * B) / (k * k);
arr.push(n);
arr.push(k);
return arr;
}
const L = 2, B = 4;
const result = minimumSquares(L, B);
console.log(result[0] + " " + result[1]);
Output
[2, 2]
Time Complexity: O(log min(L, B))
Auxiliary Space: O(1)
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!