Given two positive integers n and m. The task is to count number of parallelogram that can be formed of any size when n horizontal parallel lines intersect with m vertical parallel lines.
Examples:
Input : n = 3, m = 2
Output : 3
2 parallelograms of size 1x1 and 1 parallelogram
of size 2x1.
Input : n = 5, m = 5
Output : 100
The idea is to use Combination, which state, number of ways to choose k items from given n items is given by nCr.
To form a parallelogram, we need two horizontal parallel lines and two vertical parallel lines. So, number of ways to choose two horizontal parallel lines are nC2 and number of ways to choose two vertical parallel lines are mC2. So, total number of possible parallelogram will be nC2 x mC2.
Below is C++ implementation of this approach:
C++
// CPP Program to find number of parallelogram when // n horizontal parallel lines intersect m vertical // parallel lines.#include<bits/stdc++.h>#define MAX 10using namespace std;// Find value of Binomial Coefficientint binomialCoeff(int C[][MAX], int n, int k){ // Calculate value of Binomial Coefficient // in bottom up manner for (int i = 0; i <= n; i++) { for (int j = 0; j <= min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously // stored values else C[i][j] = C[i-1][j-1] + C[i-1][j]; } }}// Return number of parallelogram when n horizontal// parallel lines intersect m vertical parallel lines.int countParallelogram(int n, int m){ int C[MAX][MAX] = { 0 }; binomialCoeff(C, max(n, m), 2); return C[n][2] * C[m][2];}// Driver Programint main(){ int n = 5, m = 5; cout << countParallelogram(n, m) << endl; return 0;} |
Java
// Java Program to find number of parallelogram when // n horizontal parallel lines intersect m vertical // parallel lines.class GFG{ static final int MAX = 10; // Find value of Binomial Coefficient static void binomialCoeff(int C[][], int n, int k) { // Calculate value of Binomial Coefficient // in bottom up manner for (int i = 0; i <= n; i++) { for (int j = 0; j <= Math.min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously // stored values else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } } // Return number of parallelogram when n horizontal // parallel lines intersect m vertical parallel lines. static int countParallelogram(int n, int m) { int C[][]=new int[MAX][MAX]; binomialCoeff(C, Math.max(n, m), 2); return C[n][2] * C[m][2]; } // Driver code public static void main(String arg[]) { int n = 5, m = 5; System.out.println(countParallelogram(n, m)); }}// This code is contributed By Anant Agarwal. |
Python3
# Python Program to find number of parallelogram when# n horizontal parallel lines intersect m vertical# parallel lines.MAX = 10;# Find value of Binomial Coefficientdef binomialCoeff(C, n, k): # Calculate value of Binomial Coefficient # in bottom up manner for i in range(n + 1): for j in range(0, min(i, k) + 1): # Base Cases if (j == 0 or j == i): C[i][j] = 1; # Calculate value using previously # stored values else: C[i][j] = C[i - 1][j - 1] + C[i - 1][j];# Return number of parallelogram when n horizontal# parallel lines intersect m vertical parallel lines.def countParallelogram(n, m): C = [[0 for i in range(MAX)] for j in range(MAX)] binomialCoeff(C, max(n, m), 2); return C[n][2] * C[m][2];# Driver codeif __name__ == '__main__': n = 5; m = 5; print(countParallelogram(n, m));# This code is contributed by 29AjayKumar |
C#
// C# Program to find number of parallelogram when // n horizontal parallel lines intersect m vertical // parallel lines.using System;class GFG{ static int MAX = 10; // Find value of Binomial Coefficient static void binomialCoeff(int [,]C, int n, int k) { // Calculate value of Binomial Coefficient // in bottom up manner for (int i = 0; i <= n; i++) { for (int j = 0; j <= Math.Min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i, j] = 1; // Calculate value using previously // stored values else C[i, j] = C[i - 1, j - 1] + C[i - 1, j]; } } } // Return number of parallelogram when n horizontal // parallel lines intersect m vertical parallel lines. static int countParallelogram(int n, int m) { int [,]C = new int[MAX, MAX]; binomialCoeff(C, Math.Max(n, m), 2); return C[n, 2] * C[m, 2]; } // Driver code public static void Main() { int n = 5, m = 5; Console.WriteLine(countParallelogram(n, m)); }}// This code is contributed By vt_m. |
Javascript
<script>// Javascript Program to find number of parallelogram when // n horizontal parallel lines intersect m vertical // parallel lines.var MAX = 10;// Find value of Binomial Coefficientfunction binomialCoeff(C, n, k){ // Calculate value of Binomial Coefficient // in bottom up manner for (var i = 0; i <= n; i++) { for (var j = 0; j <= Math.min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously // stored values else C[i][j] = C[i-1][j-1] + C[i-1][j]; } }}// Return number of parallelogram when n horizontal// parallel lines intersect m vertical parallel lines.function countParallelogram(n, m){ var C = Array.from(Array(MAX), () => Array(MAX).fill(0)); binomialCoeff(C, Math.max(n, m), 2); return C[n][2] * C[m][2];}// Driver Programvar n = 5, m = 5; document.write( countParallelogram(n, m));// This code is contributed by rdtank.</script> |
Output
100
Time Complexity: O(n2)
Auxiliary Space: O(n2)
Approach: Using Basic Maths
The same Question can be Solved By just using the basic maths
as we know nC2 = n*(n-1)/2 and same for mC2 so just using basic maths we can solve the question in O(1)
Below is the implementation of the above approach:
C++
#include <iostream>class GFG {public: static int findtheParallelogram(int n, int m) { // as nC2 = (n*(n-1))/2 int result = ((n * (n - 1)) / 2) * ((m * (m - 1)) / 2); return result; }};int main(){ int n = 5; int m = 5; std::cout << GFG::findtheParallelogram(n, m) << std::endl; return 0;} |
Java
import java.io.*;class GFG { public static int findtheParallelogram(int n, int m) { //as nC2 = (n*(n-1))/2 int result = ((n * (n - 1)) / 2) * ((m * (m - 1)) / 2); return result; } //Driver code public static void main(String[] vars){ int n = 5; int m =5; System.out.println(findtheParallelogram(n,m)); }} |
C#
using System;class GFG { // This method calculates the number of parallelograms // that can be formed given the dimensions n and m, // where n and m are the number of rows and columns. public static int FindTheParallelogram(int n, int m) { // Calculate nC2 = (n * (n - 1)) / 2 // This formula represents the number of ways to // choose 2 items from n. For a parallelogram, we // need to choose 2 rows from n and 2 columns from // m. int result = ((n * (n - 1)) / 2) * ((m * (m - 1)) / 2); return result; }}class Program { static void Main(string[] args) { int n = 5; int m = 5; // Calculate and display the number of // parallelograms that can be formed with the given // dimensions n and m. Console.WriteLine("Number of Parallelograms: " + GFG.FindTheParallelogram(n, m)); }} |
Output
100
Time Complexity :O(1)
Space Complexity : O(1)
This article is contributed by Aarti_Rathi and Dhruv Khoradiya. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
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!
