Number of rectangles with given area in an N*M grid

0 0 8 minutes read

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.

Input: N = 2, M = 2, A = 3
Output: 0
Explanation:
The possible rectangles with area A (= 3) are of dimensions either 1 × 3 or 3 × 1.
But, the maximum length of a side in the grid can only be 2. Therefore, no rectangles can be inscribed within the grid.

Approach: The problem can be solved based on the following observations:

The total number of ways to select a segment of length X on the segment of length M is equal to (M – X + 1).
Therefore, the total count of rectangles of size X * Y in the rectangle of size M * N is equal to (M – X + 1) * (N – Y + 1).

Follow the steps below to solve the problem:

Iterate over the range [1, √A]. For every i^th iteration, find all possible values of length and breadth of the rectangles, say { i, (A / i)} or { (A / i), i } within the given grid.
Iterate over all possible values of length say X and breadth say, Y and increment the count of rectangles by (M – X + 1) * (N – Y + 1).
Finally, print the count obtained.

Below is the implementation of the above approach:

C++

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of rectangles
// in an M * N grid such that the area of
// the rectangles is equal to A
int count_number(int N, int M, int A)
{
 
    // Stores all possible values of length
    // and breadth whose area equal to A
    vector<pair<int, int> > v;
 
    // Calculate all divisors of A
    for (int i = 1; i * i <= A; i++) {
 
        // If N is divisible by i
        if (N % i == 0) {
 
            // Stores length of the rectangle
            int length = i;
 
            // Stores breadth of the rectangle
            int breadth = A / i;
 
            // If length of rectangle is not
            // equal to breadth of rectangle
            if (length != breadth) {
 
                // Insert { length, breadth }
                v.push_back({ length, breadth });
 
                // Insert { breadth, length }
                v.push_back({ breadth, length });
            }
            else {
 
                // Insert { length, breadth}
                // because both are equal
                v.push_back({ length, breadth });
            }
        }
    }
 
    // Stores the count of rectangles
    // in a grid whose area equal to A
    long long total = 0;
 
    // Iterate over all possible
    // values of { length, breadth }
    for (auto it : v) {
 
        // Stores total count of ways to
        // select a segment of length it.first
        // on the segment of length M
        int num1 = (max(0, M - it.first + 1));
 
        // Stores total count of ways to
        // select a segment of length it.second
        // on the segment of length N
        int num2 = (max(0, N - it.second + 1));
 
        // Update total
        total += (num1 * num2);
    }
 
    return total;
}
 
// Drivers Code
int main()
{
 
    // Input
    int N = 2, M = 2, A = 2;
 
    // Print the result
    cout << count_number(N, M, A) << endl;
}

Java

// Java program of the above approach
import java.util.*;
class GFG
{
     
static class pair
{ 
    int first, second; 
    public pair(int first, int second)  
    { 
        this.first = first; 
        this.second = second; 
    }    
} 
   
// Function to find the count of rectangles
// in an M * N grid such that the area of
// the rectangles is equal to A
static int count_number(int N, int M, int A)
{
 
    // Stores all possible values of length
    // and breadth whose area equal to A
    Vector<pair> v = new Vector<pair>();
 
    // Calculate all divisors of A
    for (int i = 1; i * i <= A; i++) 
    {
 
        // If N is divisible by i
        if (N % i == 0)
        {
 
            // Stores length of the rectangle
            int length = i;
 
            // Stores breadth of the rectangle
            int breadth = A / i;
 
            // If length of rectangle is not
            // equal to breadth of rectangle
            if (length != breadth) 
            {
 
                // Insert { length, breadth }
                v.add(new pair(length, breadth));
 
                // Insert { breadth, length }
                v.add(new pair(breadth, length));
            }
            else
            {
 
                // Insert { length, breadth}
                // because both are equal
                v.add(new pair(length, breadth));
            }
        }
    }
 
    // Stores the count of rectangles
    // in a grid whose area equal to A
    int total = 0;
 
    // Iterate over all possible
    // values of { length, breadth }
    for (pair it : v)
    {
 
        // Stores total count of ways to
        // select a segment of length it.first
        // on the segment of length M
        int num1 = (Math.max(0, M - it.first + 1));
 
        // Stores total count of ways to
        // select a segment of length it.second
        // on the segment of length N
        int num2 = (Math.max(0, N - it.second + 1));
 
        // Update total
        total += (num1 * num2);
    }
    return total;
}
 
// Drivers Code
public static void main(String[] args)
{
 
    // Input
    int N = 2, M = 2, A = 2;
 
    // Print the result
    System.out.print(count_number(N, M, A) +"\n");
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program of the above approach
 
# Function to find the count of rectangles
# in an M * N grid such that the area of
# the rectangles is equal to A
def count_number(N, M, A):
 
    # Stores all possible values of length
    # and breadth whose area equal to A
    v = []
 
    # Calculate all divisors of A
    for i in range(1, A + 1):
 
        if i * i > A:
            break
 
        # If N is divisible by i
        if (N % i == 0):
 
            # Stores length of the rectangle
            length = i
 
            # Stores breadth of the rectangle
            breadth = A // i
 
            # If length of rectangle is not
            # equal to breadth of rectangle
            if (length != breadth):
 
                # Insert { length, breadth }
                v.append([length, breadth ])
 
                # Insert { breadth, length }
                v.append([breadth, length ])
            else:
                # Insert { length, breadth}
                # because both are equal
                v.append([length, breadth ])
 
    # Stores the count of rectangles
    # in a grid whose area equal to A
    total = 0
 
    # Iterate over all possible
    # values of { length, breadth }
    for it in v:
 
        # Stores total count of ways to
        # select a segment of length it.first
        # on the segment of length M
        num1 = (max(0, M - it[0] + 1))
 
        # Stores total count of ways to
        # select a segment of length it.second
        # on the segment of length N
        num2 = (max(0, N - it[1] + 1))
 
        # Update total
        total += (num1 * num2)
    return total
 
# Drivers Code
if __name__ == '__main__':
 
    # Input
    N, M, A = 2, 2, 2
 
    # Print the result
    print(count_number(N, M, A))
 
# This code is contributed by mohit kumar 29.

C#

// C# implementation of the approach 
using System; 
using System.Collections.Generic; 
class GFG 
{
 
  public class pair  
  {  
    public int first, second;  
    public pair(int first, int second)  
    {  
      this.first = first;  
      this.second = second;  
    }  
  }
 
  // Function to find the count of rectangles
  // in an M * N grid such that the area of
  // the rectangles is equal to A
  static int count_number(int N, int M, int A)
  {
 
    // Stores all possible values of length
    // and breadth whose area equal to A
    List<pair> v = new List<pair>(); 
 
    // Calculate all divisors of A
    for (int i = 1; i * i <= A; i++) 
    {
 
      // If N is divisible by i
      if (N % i == 0)
      {
 
        // Stores length of the rectangle
        int length = i;
 
        // Stores breadth of the rectangle
        int breadth = A / i;
 
        // If length of rectangle is not
        // equal to breadth of rectangle
        if (length != breadth) 
        {
 
          v.Add(new pair(length, breadth));
 
          // Insert { breadth, length }
          v.Add(new pair(breadth, length));
        }
        else
        {
 
          // Insert { length, breadth}
          // because both are equal
          v.Add(new pair(length, breadth));
        }
      }
    }
 
    // Stores the count of rectangles
    // in a grid whose area equal to A
    int total = 0;
 
    // Iterate over all possible
    // values of { length, breadth }
    foreach (pair it in v)
    {
 
      // Stores total count of ways to
      // select a segment of length it.first
      // on the segment of length M
      int num1 = (Math.Max(0, M - it.first + 1));
 
      // Stores total count of ways to
      // select a segment of length it.second
      // on the segment of length N
      int num2 = (Math.Max(0, N - it.second + 1));
 
      // Update total
      total += (num1 * num2);
    }
    return total;
  }
 
  // Driver code 
  public static void Main(String[] args) 
  { 
    // Input
    int N = 2, M = 2, A = 2;
 
    // Print the result
    Console.Write(count_number(N, M, A) +"\n");
  } 
} 
 
// This code is contributed by susmitakundugoaldang

Javascript

<script>
// Javascript program of the above approach
 
class pair
{
    constructor(first,second)
    {
        this.first = first;
        this.second = second;
    }
}
 
function count_number(N,M,A)
{
    // Stores all possible values of length
    // and breadth whose area equal to A
    let v = [];
  
    // Calculate all divisors of A
    for (let i = 1; i * i <= A; i++)
    {
  
        // If N is divisible by i
        if (N % i == 0)
        {
  
            // Stores length of the rectangle
            let length = i;
  
            // Stores breadth of the rectangle
            let breadth = A / i;
  
            // If length of rectangle is not
            // equal to breadth of rectangle
            if (length != breadth)
            {
  
                // Insert { length, breadth }
                v.push(new pair(length, breadth));
  
                // Insert { breadth, length }
                v.push(new pair(breadth, length));
            }
            else
            {
  
                // Insert { length, breadth}
                // because both are equal
                v.push(new pair(length, breadth));
            }
        }
    }
  
    // Stores the count of rectangles
    // in a grid whose area equal to A
    let total = 0;
  
    // Iterate over all possible
    // values of { length, breadth }
    for (let it=0;it< v.length;it++)
    {
  
        // Stores total count of ways to
        // select a segment of length it.first
        // on the segment of length M
        let num1 = (Math.max(0, M - v[it].first + 1));
  
        // Stores total count of ways to
        // select a segment of length it.second
        // on the segment of length N
        let num2 = (Math.max(0, N - v[it].second + 1));
  
        // Update total
        total += (num1 * num2);
    }
    return total;
}
 
// Drivers Code
// Input
let N = 2, M = 2, A = 2;
  
// Print the result
document.write(count_number(N, M, A) +"<br>");
 
 
// This code is contributed by unknown2108
</script>

Output:

Time Complexity: O(sqrt(N))
Auxiliary Space: O(sqrt(N))

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!