Last Updated: 22 Dec, 2020
Number of rectangles in a grid
Easy
Asked in companies
You are given an arbitrary grid with M rows and N columns. You have to print the total number of rectangles which can be formed using the rows and columns of this grid. In simple words, print the number of unique rectangles in the grid.
For example:
Consider the grid shown below. The dark black boundary encloses a grid of dimension 3x4.
The green colour represents rectangles of dimension 1x1.
The brown colour represents the rectangles of dimension 1x2.
The blue colour represents the rectangles of dimension 2x2.
The red colour represents the rectangles of dimension 3x3.
The yellow colour represents the rectangles of dimension 3x1.
There can be many different other possibilities as well. You need to print the total number of all such rectangles.
Note:
Two rectangles are said to be unique if atleast one of their 4 sides is non-overlapping.
Input Format:
The first line of the input contains a single integer T, representing the number of test cases.
The first and only line of each test case contains two space-separated positive integers, representing the values of M(number of rows) and N(number of columns) respectively.
Output Format:
For each test case, print the number of rectangles which can be formed using the rows and columns of the given grid.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N, M <= 10^4
Time Limit: 1sec
Follow Up:
Try to solve this problem in O(1) time.
Approaches
If we look carefully at the given problem, we observe that to create a rectangle in a grid, we just need to select two horizontal and two vertical lines among all the lines present in the grid.
In a grid with N columns, we know that there are (N+1) vertical lines.
Also, in a grid with M rows, there are (N+1) horizontal lines (including the outer boundaries as well).
To better understand this approach, consider the grid shown below:-
This grid had 3 rows and 4 columns. Hence, M=3 and N=4. Vertical lines are coloured red and horizontal lines are coloured yellow.
As is clearly visible, there are (M+1) = 4 horizontal lines and there are (N+1) = 5 vertical lines.
Now, to select two horizontal lines out of 4, there are 4C2(=6) ways.
Similarly, to select two vertical lines out of 5, there are 5C2(=10) number of ways.
Total number of ways to select two vertical and two horizontal lines out of five vertical and four horizontal lines is = (6*10) = 60. Hence, there are total of 60 rectangles in the given grid.
Our formula becomes → (M+1)C2 * (N+1)C2, where nCr is defined as the total number of unique ways to choose r objects from a set containing n different objects.
On simplification, this formula evaluates to → (M*(M+1)*N*(N+1))/4.
We can directly use this formula to get the total number of rectangles in a given grid with M rows and N columns.