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 = NC2 and the Number of ways to select two lines parallel to Y axis = MC2 .
- So the total number of rectangles = NC2 * MC2 = [ 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 rectanglesint 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 Programint 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 axisclass GFG{// Function to calculate// number of rectanglesstatic 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 Programpublic 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 axisdef 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 codeN = 3M = 6print(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 axisusing System;class GFG{// Function to calculate// number of rectanglesstatic 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 Programpublic 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 rectanglesfunction 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> |
45
Time Complexity: O(1), as constant operations are being performed.
Auxiliary Space: O(1), as constant space is being used.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
