Tutorialspoint.dev

Number of rectangles in N*M grid

We are given a N*M grid, print the number of rectangles in it.

Examples:

Input  : N = 2, M = 2
Output : 9
There are 4 rectangles of size 1 x 1.
There are 2 rectangles of size 1 x 2
There are 2 rectangles of size 2 x 1
There is one rectangle of size 1 x 1.

Input  : N = 5, M = 4
Output : 150

Input :  N = 4, M = 3
Output: 60



We have discussed counting number of squares in a n x m grid,

Let us derive a formula for number of rectangles.

If the grid is 1×1, there is 1 rectangle.
If the grid is 2×1, there will be 2 + 1 = 3 rectangles
If it grid is 3×1, there will be 3 + 2 + 1 = 6 rectangles.
we can say that for N*1 there will be N + (N-1) + (n-2) … + 1 = (N)(N+1)/2 rectangles

If we add one more column to N×1, firstly we will have as many rectangles in the 2nd column as the first,
and then we have that same number of 2×M rectangles.
So N×2 = 3 (N)(N+1)/2

After deducing this we can say
For N*M we’ll have (M)(M+1)/2 (N)(N+1)/2 = M(M+1)(N)(N+1)/4

So the formula for total rectangles will be M(M+1)(N)(N+1)/4

C++

// C++ program to count number of rectangles
// in a n x m grid
#include <bits/stdc++.h>
using namespace std;
  
int rectCount(int n, int m)
{
    return (m * n * (n + 1) * (m + 1)) / 4;
}
  
/* driver code */
int main()
{
    int n = 5, m = 4;
    cout << rectCount(n, m);
    return 0;
}

Java

// JAVA Code to count number of 
// rectangles in N*M grid
import java.util.*;
  
class GFG {
      
    public static long  rectCount(int n, int m)
    {
        return (m * n * (n + 1) * (m + 1)) / 4;
    }
      
    /* Driver program to test above function */
    public static void main(String[] args) 
    {
        int n = 5, m = 4;
       System.out.println(rectCount(n, m));
    }
}
  
// This code is contributed by Arnav Kr. Mandal.

Python3

# Python3 program to count number 
# of rectangles in a n x m grid
  
def rectCount(n, m):
  
    return (m * n * (n + 1) * (m + 1)) // 4
  
# Driver code 
n, m = 5, 4
print(rectCount(n, m))
  
# This code is contributed by Anant Agarwal.

C#

// C# Code to count number of 
// rectangles in N*M grid
using System;
  
class GFG {
       
    public static long  rectCount(int n, int m)
    {
        return (m * n * (n + 1) * (m + 1)) / 4;
    }
       
    // Driver program 
    public static void Main() 
    {
        int n = 5, m = 4;
       Console.WriteLine(rectCount(n, m));
    }
}
   
// This code is contributed by Anant Agarwal.

PHP

<?php
// PHP program to count 
// number of rectangles
// in a n x m grid
  
function rectCount($n, $m)
{
    return ($m * $n
           ($n + 1) * 
           ($m + 1)) / 4;
}
  
// Driver Code
$n = 5;
$m = 4;
echo rectCount($n, $m);
  
// This code is contributed
// by ajit
?>


Output:

150

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter