Open In App

Cutting Rectangles

Last Updated : 11 Apr, 2023
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

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)



Similar Reads

Probability of cutting a rope into three pieces such that the sides form a triangle
Given a rope. We have to find the probability of cutting a rope into 3 pieces such that they form a triangle. Answer: 0.25 Explanation: Let the length of rope be 1 unit. We choose two points X and Y on the rope. Note: Formation of triangle is based on Triangle inequality i.e. sum of the lengths of any two sides of a triangle must be greater than th
2 min read
Maximum length possible by cutting N given woods into at least K pieces
Given an array wood[] of size N, representing the length of N pieces of wood and an integer K, at least K pieces of the same length need to be cut from the given wooden pieces. The task is to find the maximum possible length of these K wooden pieces that can be obtained. Examples: Input: wood[] = {5, 9, 7}, K = 3 Output: 5 Explanation: Cut arr[0] =
8 min read
Maximum length of all possible K equal length ropes generated by cutting N ropes
Given an array arr[] consisting of N positive integers representing the lengths of N ropes and a positive integer K, the task is to find the maximum length of the rope that has a frequency of at least K by cutting any ropes in any number of pieces. Examples: Input: arr[] = {5, 2, 7, 4, 9}, K = 5Output: 4Explanation:Below are the possible cutting of
8 min read
Maximize minimum sweetness in cake cutting
Given that cake consists of N chunks, whose individual sweetness is represented by the sweetness[] array, the task is to cut the cake into K + 1 pieces to maximize the minimum sweetness. Examples: Input: N = 6, K = 2, sweetness[] = {6, 3, 2, 8, 7, 5}Output: 9Explanation: Divide the cake into [6, 3], [2, 8], [7, 5] with sweetness levels 9, 10, and 1
7 min read
Maximizing Profit in Ribbon Cutting with Minimized Costs
Given a collection of ribbons, each of which has a certain length and can be sold at a specific price. However, to sell we need to make sure they are of equal length but there's a cost associated with cutting the ribbons into smaller pieces. The objective is to maximize the total profit by selecting an optimal ribbon length for cutting and making t
8 min read
Number of ways of cutting a Matrix such that atleast one cell is filled in each part
Given an integer K and a matrix mat[][] containing 1 and 0, where 1 denotes the cell is filled and 0 denotes an empty cell. The task is to find the number of ways to cut the matrix into K parts using K-1 cuts such that each part of the matrix contains atleast one filled cell. For each cut, there must be a direction either horizontal or vertical. Th
12 min read
CSES Solutions - Rectangle Cutting
Given an A X B rectangle, your task is to cut it into squares. On each move you can select a rectangle and cut it into two rectangles in such a way that all side lengths remain integers. What is the minimum possible number of moves? Examples: Input: A = 3, B = 5Output: 3Explanation: The three moves required to cut the rectangle into squares are: Cu
8 min read
Maximum Product Cutting | DP-36
Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Assume that the length of rope is more than 2 meters.  Examples:  Input: n = 2Output: 1 (Maximum obtainable product is 1*1)Input: n = 3Output: 2 (Maximum obtainable product is 1
15+ min read
Rod Cutting
Given a rod of length n inches and an array of prices that includes prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. We are mainly given a price array such that the size of the price array is same as rod length and price[i] represents price of length i+1 Input : price[
15+ min read
Create a matrix with alternating rectangles of O and X
Write a code which inputs two numbers m and n and creates a matrix of size m x n (m rows and n columns) in which every elements is either X or 0. The Xs and 0s must be filled alternatively, the matrix should have outermost rectangle of Xs, then a rectangle of 0s, then a rectangle of Xs, and so on. Examples: Input: m = 3, n = 3 Output: Following mat
15 min read
Sum of Areas of Rectangles possible for an array
Given an array, the task is to compute the sum of all possible maximum area rectangles which can be formed from the array elements. Also, you can reduce the elements of the array by at most 1. Examples: Input: a = {10, 10, 10, 10, 11, 10, 11, 10} Output: 210 Explanation: We can form two rectangles one square (10 * 10) and one (11 * 10). Hence, tota
13 min read
Intersecting rectangle when bottom-left and top-right corners of two rectangles are given
Given coordinates of 4 points, bottom-left and top-right corners of two rectangles. The task is to find the coordinates of the intersecting rectangle formed by the given two rectangles. Examples: Input: rec1: bottom-left(0, 0), top-right(10, 8), rec2: bottom-left(2, 3), top-right(7, 9) Output: (2, 3) (7, 8) (2, 8) (7, 3) Input: rec1: bottom-left(0,
10 min read
Smallest square formed with given rectangles
Given a rectangle of length l and breadth b, we need to find the area of the smallest square which can be formed with the rectangles of these given dimensions. Examples: Input : 1 2 Output : 4 We can form a 2 x 2 square using two rectangles of size 1 x 2. Input : 7 10 Output :4900 Let's say we want to make a square of side length a from rectangles
6 min read
Check if it is possible to rearrange rectangles in a non-ascending order of breadths
Given n number of rectangles with it's L-length and B-Breadth. We can turn any rectangle by 90 degrees. In other words, after turning them, the breadth will become length and length will be breadth. The task is to check if there is a way to make the rectangles go in order of non-ascending breadth. That is, a breadth of every rectangle has to be not
7 min read
Find the number of rectangles of size 2*1 which can be placed inside a rectangle of size n*m
Given two integers n, m. Find the number of rectangles of size 2*1 that can be placed inside a rectangle of size n*m. Note: No two small rectangles overlap.Each small rectangle lies entirely inside the large rectangle. It is allowed to touch the edges of the large rectangle. Examples: Input : n = 3, m =3 Output : 4 Input : n = 2, m = 4 Output : 4 A
6 min read
Maximum given sized rectangles that can be cut out of a sheet of paper
Given the length L and breadth B of a sheet of paper, the task is to find the maximum number of rectangles with given length l and breadth b that can be cut from this sheet of paper.Examples: Input: L = 5, B = 2, l = 14, b = 3 Output: 0 The sheet is smaller than the required rectangle. So, no rectangle of the given dimension can be cut from the she
6 min read
Largest subset of rectangles such that no rectangle fit in any other rectangle
Given height and width of N rectangles. The task is to find the size of the largest subset such that no pair of rectangles fit within each other. Note that if H1 ? H2 and W1 ? W2 then rectangle 1 fits inside rectangle 2. Examples: Input: arr[] = {{1, 3}, {2, 2}, {1, 3}} Output: 2 The required sub-set is {{1, 3}, {2, 2}} {1, 3} is included only once
15 min read
Find the minimum number of rectangles left after inserting one into another
Given width and height of N rectangles. The task is to find the minimum number of rectangles left after inserting one into another. Note : If W1 < W2 and H1 < H2 then rectangle 1 fits inside rectangle 2.The smallest rectangle can insert in the second smallest, and this rectangle can insert in the next one and so forth. Examples: Input : arr[]
9 min read
Count of distinct rectangles inscribed in an equilateral triangle
Given an equilateral triangle made of dots (.) joined together to form triangle and an integer n which represents the length of the sides of the triangle. The task is to count the number of rectangles that can be inscribed in the given triangle such that: Horizontal edges must be parallel to the base of the given triangle.Rectangle must only be for
11 min read
Count Distinct Rectangles in N*N Chessboard
Given a N x N Chessboard. The task is to count distinct rectangles from the chessboard. For example, if the input is 8 then the output should be 36.Examples: Input: N = 4 Output: 10 Input: N = 6 Output: 21 Approach: Suppose N = 8 i.e. 8 x 8 chessboard is given, So different rectangles that can be formed are: 1 x 1, 1 x 2, 1 x 3, 1 x 4, 1 x 5, 1 x 6
3 min read
Check if N rectangles of equal area can be formed from (4 * N) integers
Given an integer N and an array arr[] of size 4 * N, the task is to check whether N rectangles of equal area can be formed from this array if each element can be used only once. Examples: Input: arr[] = {1, 8, 2, 1, 2, 4, 4, 8}, N = 2 Output: Yes Two rectangles with sides (1, 8, 1, 8) and (2, 4, 2, 4) can be formed. Both of these rectangles have th
6 min read
Count of rectangles possible from N and M straight lines parallel to X and Y axis respectively
Given two integers N and M, where N straight lines are parallel to the X-axis and M straight lines are parallel to Y-axis, the task is to calculate the number of rectangles that can be formed by these lines. Examples: Input: N = 3, M = 6 Output: 45 Explanation: There are total 45 rectangles possible with 3 lines parallel to x axis and 6 lines paral
5 min read
Minimum area of square holding two identical rectangles
Given the length L and breadth B of two identical rectangles, the task is to find the minimum area of a square in which the two identical rectangles with dimensions L × B can be embedded.Examples: Input: L = 7, B = 4 Output: 64 Explanation: Two rectangles with sides 7 x 4 can fit into square with side 8. By placing two rectangles with side 4 upon e
4 min read
Find side of Square which makes minimal area to fit two identical rectangles inside it
Given height H, and width W, of a rectangle, the task is to find the side of a square of the minimum area in which two rectangles fit completely. Note: Two rectangles can touch each other by side or corner.Rectangles cannot intersect each other.Rectangles can also touch the sides of the square but must be completely inside it.The Rectangles can be
12 min read
Missing vertex among N axis-parallel rectangles
Given N axis-parallel rectangles in a 2-D Cartesian coordinate system and coordinates of 4N-1 vertices, the task is to find the single vertex missing. Examples: Input: N = 2, V[][] = {{1, 1}, {1, 2}, {4, 6}, {2, 1}, {9, 6}, {9, 3}, {4, 3}}Output: {2, 2} Explanation: The coordinates forming an axis parallel rectangle are {4, 6}, {9, 6}, {4, 3}, {9,
9 min read
Count of Rectangles with area K made up of only 1s from given Binary Arrays
Given two binary arrays A[] and B[], of length N and M respectively, the task is to find the number of rectangles of area K consisting of 1's in the matrix C[][] generated by multiplying the two arrays such that, C[i][j] = A[i] * B[j] (1< i < n, 1< j < m). Examples: Input: N= 3, M = 3, A[] = {1, 1, 0}, B[] = {0, 1, 1}, K = 2 Output: 4 E
11 min read
Count of smaller rectangles that can be placed inside a bigger rectangle
Given four integers L, B, l, and b, where L and B denote the dimensions of a bigger rectangle and l and b denotes the dimension of a smaller rectangle, the task is to count the number of smaller rectangles that can be drawn inside a bigger rectangle. Note: Smaller rectangles can overlap partially. Examples: Input: L = 5, B = 3, l = 4, b = 1Output:
5 min read
Perimeter of the Union of Two Rectangles
Given two arrays X[] and Y[], each of length 4, where (X[0], Y[0]) and (X[1], Y[1]) represents the bottom left and top right corners of one rectangle and (X[2], Y[2]) and (X[3], Y[3]) represents the bottom left and top right corners of the other rectangle, the task is to find the perimeter of the outer boundaries of the union of the two rectangles
7 min read
Count rectangles generated in a given rectangle by lines drawn parallel to X and Y axis from a given set of points
Given a 2D array rectangle[][] representing vertices of a rectangle {(0, 0), (L, 0), (0, B), (L, B)} of dimensions L * B, and another 2D-array, points[][] of size N in a Cartesian coordinate system. Draw a horizontal line parallel to the X-axis and a vertical line parallel to the Y-axis from each point of the given array. The task is to count all p
6 min read
Number of rectangles with given area in an N*M grid
Given three positive integers N, M, and A, the task is to count the number of rectangles with area equal to A present in an M * N grid. Examples: Input: N = 2, M = 2, A = 2 Output: 4 Explanation: In the given grid of size 2 × 2, 2 rectangles of dimension 2 × 1 and 2 rectangles of dimension 1 × 2 can be inscribed. Therefore, the required output is 4
10 min read
Article Tags :
three90RightbarBannerImg