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 approach import java.util.*; class GFG{ // Function to count smaller rectangles // within the larger rectangle static 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 public 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 rectangle def 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 code if __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 approach using System; class GFG{ // Function to count smaller rectangles // within the larger rectangle static 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 public 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 rectangle function 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!