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 = 1
Output: 6
Explanation:
There are 6 rectangles of dimension 4 × 1 that can be drawn inside a bigger rectangle of dimension 5 × 3.Input: L = 3, B = 2, l = 2, b = 1
Output: 3
Explanation:
There are 3 rectangles of dimension 3 × 2 can be drawn inside a bigger rectangle of dimension 2 × 1.
Naive Approach: The idea is to iterate over the length L and breadth B of the bigger rectangle to count the number of smaller rectangles of dimension l x b that can be drawn within the range of bigger rectangle. Print the total count after the traversal.
Time Complexity: O(L * B)
Auxiliary Space: O(1)
Efficient Approach: The above problem can be solved using Permutation and Combinations. Below are the steps:
- The total possible values of the length of smaller rectangle l using the length L is given by (L – l + 1).
- The total possible values of the breadth of smaller rectangle b using the length B is given by (B – b + 1).
- Hence, the total number of possible rectangles can be formed is given by:
(L – l + 1) * (B – b + 1)
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count smaller rectangles // within the larger rectangle int No_of_rectangles(int L, int B, int l, int b) { // If the dimension of the smaller // rectangle is greater than the // bigger one if ((l > L) || (b > B)) { return -1; } else { // Return the number of smaller // rectangles possible return (L - l + 1) * (B - b + 1); } } // Driver Code int main() { // Dimension of bigger rectangle int L = 5, B = 3; // Dimension of smaller rectangle int l = 4, b = 1; // Function call cout << No_of_rectangles(L, B, l, b); return 0; } |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count smaller rectangles// within the larger rectanglestatic int No_of_rectangles(int L, int B, int l, int b){ // If the dimension of the smaller // rectangle is greater than the // bigger one if ((l > L) || (b > B)) { return -1; } else { // Return the number of smaller // rectangles possible return (L - l + 1) * (B - b + 1); }}// Driver Codepublic static void main(String[] args){ // Dimension of bigger rectangle int L = 5, B = 3; // Dimension of smaller rectangle int l = 4, b = 1; // Function call System.out.println(No_of_rectangles(L, B, l, b));}}// This code is contributed by jana_sayantan |
Python3
# Python3 program for the above approach# Function to count smaller rectangles# within the larger rectangledef No_of_rectangles( L, B, l, b): # If the dimension of the smaller # rectangle is greater than the # bigger one if (l > L) or (b > B): return -1; else: # Return the number of smaller # rectangles possible return (L - l + 1) * (B - b + 1); # Driver codeif __name__ == '__main__': # Dimension of bigger rectangle L = 5 B = 3 # Dimension of smaller rectangle l = 4 b = 1 # Function call print(No_of_rectangles(L, B, l, b))# This code is contributed by jana_sayantan |
C#
// C# program for the above approachusing System;class GFG{// Function to count smaller rectangles// within the larger rectanglestatic int No_of_rectangles(int L, int B, int l, int b){ // If the dimension of the smaller // rectangle is greater than the // bigger one if ((l > L) || (b > B)) { return -1; } else { // Return the number of smaller // rectangles possible return (L - l + 1) * (B - b + 1); }}// Driver Codepublic static void Main(String[] args){ // Dimension of bigger rectangle int L = 5, B = 3; // Dimension of smaller rectangle int l = 4, b = 1; // Function call Console.Write(No_of_rectangles(L, B, l, b));}}// This code is contributed by jana_sayantan |
Javascript
<script>// JavaScript implementation of the above approach// Function to count smaller rectangles// within the larger rectanglefunction No_of_rectangles(L, B, l, b){ // If the dimension of the smaller // rectangle is greater than the // bigger one if ((l > L) || (b > B)) { return -1; } else { // Return the number of smaller // rectangles possible return (L - l + 1) * (B - b + 1); }}// Driver code // Dimension of bigger rectangle let L = 5, B = 3; // Dimension of smaller rectangle let l = 4, b = 1; // Function call document.write(No_of_rectangles(L, B, l, b)); // This code is contributed by code_hunt.</script> |
6
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
