- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Given the task is to find the maximum number of parallelograms that can be made using given N number of line segments if each line segment can be used at most in one parallelogram.

Let’s now understand what we have to do using an example −

**Input** − Arr[] = {8, 3, 1, 3, 8, 7, 1, 3, 5, 3}

**Output** − 2

**Explanation** − With the above given line segments, the two parallelograms that can be formed are with sides 8, 1, 8, 1 and 3, 3, 3, 3 respectively.

**Input** − Arr[] = {7, 9, 9, 7}

**Output** − 1

The maximum number of parallelograms that can be made will be = Parallelograms that can be made with 4 equal or similar sides plus parallelograms that can be made using 2 similar sides.

In function MaxParr(), initialize a variable L = Arr[0] which will be used as the size of the array that will be used to store the frequencies of the line segments.

Loop from i=1 till i<N and check if (Arr[i] > L), and inside the if statement put L=Arr[i]. Outside the loop increase the size of L by 1.

Then initialize the frequency array int Freq[L] = {0}. Loop from i=0 till i<N and increase occurrence of each segment by 1.

The initialize count = 0 of type int to store the final count of parallelograms.

Loop from i=0 till i<L and check for parallelograms that can be made with 4 similar sides and if found then increase the value of count accordingly.

Initialize left=0 of type int to store the number of parallelograms that can be formed using 2 similar sides.

Finally loop from i=0 till i<L and check if(Freq[i] >= 2) and if so then add 1 to left.

Put count+= left/2 and return count.

#include <bits/stdc++.h> using namespace std; int MaxParr(int N, int Arr[]){ //Finding length of frequency array int L = Arr[0]; for (int i = 1; i < N; i++){ if (Arr[i] > L) L = Arr[i]; } L = L + 1; int Freq[L] = {0}; for (int i = 0; i < N; i++){ //Increasing occurrence of each line segment Freq[Arr[i]] += 1; } // To store the number of parallelograms int count = 0; for (int i = 0; i < L; i++){ /*parallelograms that can be made using 4 same sides*/ count += int(Freq[i] / 4); Freq[i] = Freq[i] % 4; } int left = 0; for (int i = 0; i < L; i++){ //Counting segments with 2 or more occurrences left if (Freq[i] >= 2) left += 1; } /*Adding parallelograms that can be formed using using 2 similar sides into the final count*/ count += left / 2; return count; } int main(){ int N = 10; int Arr[] = { 8, 3, 1, 3, 8, 7, 1, 3, 5, 3}; cout<< MaxParr(N, Arr); }

If we run the above code we will get the following output −

2

- Related Questions & Answers
- Maximum number of segments that can contain the given points in C++
- Program to find the length of the longest, that can be made using given letters in Python
- Find maximum number that can be formed using digits of a given number in C++
- Maximum number that can be display on Seven Segment Display using N segments in C++
- Maximum Number of Events That Can Be Attended in C++
- Maximum number of candies that can be bought in C
- Maximum elements that can be made equal with k updates in C++
- Klee’s Algorithm (Length Of Union Of Segments of a line) in C++
- Maximum possible intersection by moving centers of line segments in C++
- Maximize the number of segments of length p, q and r in C++
- Maximum number of segments of lengths a, b and c in C++
- Maximum number of people that can be killed with strength P in C++
- Maximum number of threads that can be created within a process in C
- Maximum Number of Vowels in a Substring of Given Length in C++
- Maximum given sized rectangles that can be cut out of a sheet of paper in C

Advertisements