Count of rectangles possible from N and M straight lines parallel to X and Y axis respectively

0 0 4 minutes read

Given two integers N and M, where N straight lines are parallel to the X-axis and M straight lines are parallel to Y-axis, the task is to calculate the number of rectangles that can be formed by these lines.

Examples:

Input: N = 3, M = 6
Output: 45
Explanation:
There are total 45 rectangles possible with 3 lines parallel to x axis and 6 lines parallel to y axis.
Input: N = 2, M = 4
Output: 6
Explanation:
There are total 6 rectangles possible with 2 lines parallel to x axis and 4 lines parallel to y axis.

Approach:
To solve the problem mentioned above we need to observe that a rectangle is formed by 4 straight lines in which opposite sides are parallel and the angle between any two sides is 90. Hence, for every rectangle, two sides need to be parallel to X-axis and the other two sides need to be parallel to Y-axis.

Number of ways to select two lines parallel to X axis = ^NC₂and the Number of ways to select two lines parallel to Y axis = ^MC₂.
So the total number of rectangles = ^NC_{2 *}^MC₂ = [ N * (N – 1) / 2 ] * [ M * (M – 1) / 2 ]

Below is implementation of above approach:

C++

// C++ Program to count number of
// rectangles formed by N lines
// parallel to X axis M lines
// parallel to Y axis
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate
// number of rectangles
int count_rectangles(int N, int M)
{
    // Total number of ways to
    // select two lines
    // parallel to X axis
    int p_x = (N * (N - 1)) / 2;
 
    // Total number of ways
    // to select two lines
    // parallel to Y axis
    int p_y = (M * (M - 1)) / 2;
 
    // Total number of rectangles
    return p_x * p_y;
}
 
// Driver Program
int main()
{
 
    int N = 3;
 
    int M = 6;
 
    cout << count_rectangles(N, M);
}

Java

// Java Program to count number of
// rectangles formed by N lines
// parallel to X axis M lines
// parallel to Y axis
class GFG{
 
// Function to calculate
// number of rectangles
static int count_rectangles(int N, int M)
{
    // Total number of ways to
    // select two lines
    // parallel to X axis
    int p_x = (N * (N - 1)) / 2;
 
    // Total number of ways
    // to select two lines
    // parallel to Y axis
    int p_y = (M * (M - 1)) / 2;
 
    // Total number of rectangles
    return p_x * p_y;
}
 
// Driver Program
public static void main(String[] args)
{
    int N = 3;
    int M = 6;
 
    System.out.print(count_rectangles(N, M));
}
}
 
// This code is contributed by sapnasingh4991

Python3

# Python3 program to count number of rectangles
# formed by N lines parallel to X axis
# and M lines parallel to Y axis
def count_rectangles(N, M):
 
    # Total number of ways to select
    # two lines parallel to X axis
    p_x = (N * (N - 1)) // 2
 
    # Total number of ways to select
    # two lines parallel to Y axis
    p_y = (M * (M - 1)) // 2
 
    # Total number of rectangles
    return p_x * p_y
 
# Driver code
N = 3
M = 6
 
print(count_rectangles(N, M))
 
# This code is contributed by himanshu77

C#

// C# Program to count number of
// rectangles formed by N lines
// parallel to X axis M lines
// parallel to Y axis
using System;
class GFG{
 
// Function to calculate
// number of rectangles
static int count_rectangles(int N, int M)
{
    // Total number of ways to
    // select two lines
    // parallel to X axis
    int p_x = (N * (N - 1)) / 2;
 
    // Total number of ways
    // to select two lines
    // parallel to Y axis
    int p_y = (M * (M - 1)) / 2;
 
    // Total number of rectangles
    return p_x * p_y;
}
 
// Driver Program
public static void Main()
{
    int N = 3;
    int M = 6;
 
    Console.Write(count_rectangles(N, M));
}
}
 
// This code is contributed by Code_mech

Javascript

<script>
 
// JavaScript Program to count number of
// rectangles formed by N lines
// parallel to X axis M lines
// parallel to Y axis
 
// Function to calculate
// number of rectangles
function count_rectangles(N, M)
{
    // Total number of ways to
    // select two lines
    // parallel to X axis
    let p_x = (N * (N - 1)) / 2;
   
    // Total number of ways
    // to select two lines
    // parallel to Y axis
    let p_y = (M * (M - 1)) / 2;
   
    // Total number of rectangles
    return p_x * p_y;
}
 
// Driver Code
 
    let N = 3;
    let M = 6;
   
    document.write(count_rectangles(N, M)); 
         
</script>

Output:

Time Complexity: O(1), as constant operations are being performed.
Auxiliary Space: O(1), as constant space is being used.

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!