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 ith 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 Aint 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 Codeint 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 approachimport 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 Astatic 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 Codepublic 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 Adef 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 Codeif __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 approachclass 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// Inputlet N = 2, M = 2, A = 2; // Print the resultdocument.write(count_number(N, M, A) +"<br>");// This code is contributed by unknown2108</script> |
Output:
4
Time Complexity: O(sqrt(N))
Auxiliary Space: O(sqrt(N))
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
