Given an array arr[] consisting of N integers, the task is to find the maximum number of pairs of array elements such that each pair has a different element and each array element can exist in only one pair
Examples:
Input: arr[] = {4, 5, 4, 5, 4}
Output: 2
Explanation:
There can be 2 pairs forms from the given array i.e., {{4, 5}, {4, 5}}. Therefore, print 2.Input: arr[] = {2, 3, 2, 1, 3, 1}
Output: 3
Approach: The given problem can be solved by storing the frequency of array elements and generate the pairs using the two highest frequency numbers. This idea can be implemented using Priority Queue. Follow the steps below to solve the problem:
- Initialize a Map, say M that stores the frequency of array elements.
- Initialize a priority queue, say, PQ, for implementing the MaxHeap and insert all the frequencies in it.
- Initialize a variable, say, count as 0 that stores the maximum count of resultant pairs.
- Traverse the priority queue PQ until its size is greater than 1 and perform the following steps:
- Pop the top two elements from the PQ.
- Decrement the value of a popped element by 1 and insert both elements again in the PQ.
- Increment the value of count by 1.
- After completing the above steps, print the value count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the maximum number// of pairs having different element// from the given arrayint maximumPairs(int a[], int n){ // Stores the frequency of // array element map<int, int> freq; // Stores maximum count of pairs int count = 0; // Increasing the frequency of // every element for (int i = 0; i < n; ++i) freq[a[i]]++; // Stores the frequencies of array // element from highest to lowest priority_queue<int> pq; for (auto itr = freq.begin(); itr != freq.end(); itr++) { // Pushing the frequencies to // the priority queue pq.push(itr->second); } // Iterate until size of PQ > 1 while (pq.size() > 1) { // Stores the top two element int freq1 = pq.top(); pq.pop(); int freq2 = pq.top(); pq.pop(); // Form the pair between the // top two pairs count++; // Decrement the frequencies freq1--; freq2--; // Insert updated frequencies // if it is greater than 0 if (freq1 > 0) pq.push(freq1); if (freq2 > 0) pq.push(freq2); } // Return the total count of // resultant pairs return count;}// Driver Codeint main(){ int arr[] = { 4, 2, 4, 1, 4, 3 }; int N = sizeof(arr) / sizeof(arr[0]); cout << maximumPairs(arr, N); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { public static int maximumPairs(int[] a, int n) { // Stores the frequency of // array element HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>(); // Stores maximum count of pairs int count = 0; // Increasing the frequency of // every element for (int i = 0; i < n; i++) { int c = a[i]; if (freq.containsKey(c)) { freq.put(c, freq.get(c) + 1); } else { freq.put(c, 1); } } // Stores the frequencies of array // element from highest to lowest PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); for (int i = 0;i<n;i++) { // Pushing the frequencies to // the priority queue if(freq.containsKey(a[i])){ pq.add(freq.get(a[i])); freq.remove(a[i]); } } // Iterate until size of PQ > 1 while (pq.size() > 1) { // Stores the top two element int freq1 = pq.poll(); int freq2 = pq.poll(); // Form the pair between the // top two pairs count++; // Decrement the frequencies freq1--; freq2--; // Insert updated frequencies // if it is greater than 0 if (freq1 > 0) pq.add(freq1); if (freq2 > 0) pq.add(freq2); } // Return the total count of // resultant pairs return count; } // Driver Code public static void main(String[] args) { int arr[] = { 4, 2, 4, 1, 4, 3 }; int N = 6; System.out.println(maximumPairs(arr, N)); }}// This code is contributed by maddler. |
Python3
# python 3 program for the above approach# Function to count the maximum number# of pairs having different element# from the given arraydef maximumPairs(a, n): # Stores the frequency of # array element freq = {} # Stores maximum count of pairs count = 0 # Increasing the frequency of # every element for i in range(n): if a[i] in freq: freq[a[i]] += 1 else: freq[a[i]] = 1 # Stores the frequencies of array # element from highest to lowest pq = [] for key,value in freq.items(): # Pushing the frequencies to # the priority queue pq.append(value) pq.sort() # Iterate until size of PQ > 1 while (len(pq) > 1): # Stores the top two element freq1 = pq[len(pq)-1] pq = pq[:-1] freq2 = pq[len(pq)-1] pq = pq[:-1] # Form the pair between the # top two pairs count += 1 # Decrement the frequencies freq1 -= 1 freq2 -= 1 # Insert updated frequencies # if it is greater than 0 if (freq1 > 0): pq.append(freq1) if (freq2 > 0): pq.append(freq2) pq.sort() # Return the total count of # resultant pairs return count# Driver Codeif __name__ == '__main__': arr = [4, 2, 4, 1, 4, 3] N = len(arr) print(maximumPairs(arr, N)) # This code is contributed by ipg2016107. |
C#
/*package whatever //do not write package name here */using System;using System.Collections.Generic;public class GFG { public static int maximumPairs(int[] a, int n) { // Stores the frequency of // array element Dictionary<int, int> freq = new Dictionary<int, int>(); // Stores maximum count of pairs int count = 0; // Increasing the frequency of // every element for (int i = 0; i < n; i++) { int c = a[i]; if (freq.ContainsKey(c)) { freq = freq + 1; } else { freq.Add(c, 1); } } // Stores the frequencies of array // element from highest to lowest Queue<int> pq = new Queue<int>(); for (int i = 0; i < n; i++) { // Pushing the frequencies to // the priority queue if (freq.ContainsKey(a[i])) { pq.Enqueue(freq[a[i]]); freq.Remove(a[i]); } } // Iterate until size of PQ > 1 while (pq.Count > 1) { // Stores the top two element int freq1 = pq.Dequeue(); int freq2 = pq.Dequeue(); // Form the pair between the // top two pairs count++; // Decrement the frequencies freq1--; freq2--; // Insert updated frequencies // if it is greater than 0 if (freq1 > 0) pq.Enqueue(freq1); if (freq2 > 0) pq.Enqueue(freq2); } // Return the total count of // resultant pairs return count; } // Driver Code public static void Main(String[] args) { int []arr = { 4, 2, 4, 1, 4, 3 }; int N = 6; Console.WriteLine(maximumPairs(arr, N)); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program for the above approach// Function to count the maximum number// of pairs having different element// from the given arrayfunction maximumPairs(a, n){ // Stores the frequency of // array element var freq = new Map(); // Stores maximum count of pairs var count = 0; // Increasing the frequency of // every element for (var i = 0; i < n; ++i) { if(freq.has(a[i])) freq.set(a[i], freq.get(a[i])+1) else freq.set(a[i],1) } // Stores the frequencies of array // element from highest to lowest var pq = [...freq.values()]; pq.sort((a,b)=>a-b); // Iterate until size of PQ > 1 while (pq.length > 1) { // Stores the top two element var freq1 = pq[pq.length-1]; pq.pop(); var freq2 = pq[pq.length-1]; pq.pop(); // Form the pair between the // top two pairs count++; // Decrement the frequencies freq1--; freq2--; // Insert updated frequencies // if it is greater than 0 if (freq1 > 0) pq.push(freq1); if (freq2 > 0) pq.push(freq2); pq.sort((a,b)=>a-b); } // Return the total count of // resultant pairs return count;}// Driver Codevar arr = [4, 2, 4, 1, 4, 3 ];var N = arr.length;document.write( maximumPairs(arr, N));// This code is contributed by rrrtnx.</script> |
Output
3
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Another Approach:
This problem can also be solved by just storing the frequency of every elements in an array. After that we need to find the maximum frequency of an element in the given array. It is confirmed that a pair can not have same values. Suppose we have the elements arr[]={1,1,1,1,2} then one pair will be formed since there is two different values present in the array. Therefore, pairs can not be formed if we are left with the element having same values.
Below is the implementation :
C++
#include <bits/stdc++.h>using namespace std;int main(){ int arr[] = { 4, 2, 4, 1, 4, 3 }; int n = sizeof(arr) / sizeof(arr[0]); int maxi = 0, remain, ans; // stores the frequency array map<int, int> freq; for (int i = 0; i < n; i++) { freq[arr[i]]++; } for (auto it : freq) { // maxi stores the maximum // frequency of an element maxi = max(maxi, it.second); } // it stores the sum of all the frequency // other than the element which has maximum frequency remain = n - maxi; if (maxi >= remain) { // there will be always zero // or more element // which will not participate in making pairs ans = remain; } else { // if n is odd then except one element // we can always form pair for every element // if n is even then all the elements can form pair ans = n / 2; } cout << ans; freq.clear(); return 0;} |
Java
import java.util.*;class GFG{ public static void main(String[] args) { int arr[] = { 4, 2, 4, 1, 4, 3 }; int n = arr.length; int maxi = 0, remain, ans; // stores the frequency array HashMap<Integer,Integer> freq = new HashMap<>(); for (int i = 0; i < n; i++) { if(freq.containsKey(arr[i])){ freq.put(arr[i], freq.get(arr[i])+1); } else{ freq.put(arr[i], 1); } } for (Map.Entry<Integer,Integer> it : freq.entrySet()) { // maxi stores the maximum // frequency of an element maxi = Math.max(maxi, it.getValue()); } // it stores the sum of all the frequency // other than the element which has maximum frequency remain = n - maxi; if (maxi >= remain) { // there will be always zero // or more element // which will not participate in making pairs ans = remain; } else { // if n is odd then except one element // we can always form pair for every element // if n is even then all the elements can form pair ans = n / 2; } System.out.print(ans); }}// This code is contributed by Rajput-Ji |
Python3
# Python program for the above approacharr = [ 4, 2, 4, 1, 4, 3 ]n = len(arr)maxi = 0# stores the frequency arrayfreq= dict()for i in range(n): if arr[i] in freq.keys(): freq[arr[i]] += 1 else: freq[arr[i]] = 1for it in freq: # maxi stores the maximum # frequency of an element maxi = max(maxi, freq[it]) # it stores the sum of all the frequency# other than the element which has maximum frequencyremain = n - maxiif(maxi >= remain): # there will be always zero # or more element # which will not participate in making pairs ans = remainelse: # if n is odd then except one element # we can always form pair for every element # if n is even then all the elements can form pair ans = n//2print(ans)freq.clear()# This code is contributed by Pushpesh Raj |
C#
using System;using System.Collections;using System.Collections.Generic;class GFG{public static void Main(){ int []arr = { 4, 2, 4, 1, 4, 3 }; int n = arr.Length; int maxi = 0, remain, ans; // stores the frequency array Dictionary<int, int> freq = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { if (freq.ContainsKey(arr[i])) { freq[arr[i]] = freq[arr[i]] + 1; } else { freq.Add(arr[i], 1); } } foreach (KeyValuePair<int, int> it in freq) { // maxi stores the maximum // frequency of an element maxi = Math.Max(maxi, it.Value); } // it stores the sum of all the frequency // other than the element which has maximum frequency remain = n - maxi; if (maxi >= remain) { // there will be always zero // or more element // which will not participate in making pairs ans = remain; } else { // if n is odd then except one element // we can always form pair for every element // if n is even then all the elements can form pair ans = n / 2; } Console.Write(ans);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>let arr = [4, 2, 4, 1, 4, 3];let n = arr.length;let maxi = 0, remain, ans; // stores the frequency arraylet freq = new Map();for (let i = 0; i < n; i++) { if (freq.has(arr[i])) { freq.set(arr[i], freq.get(arr[i]) + 1); } else { freq.set(arr[i], 1); }}for (let it of freq){ // maxi stores the maximum // frequency of an element maxi = Math.max(maxi, it[1]);}// it stores the sum of all the frequency// other than the element which has maximum frequencyremain = n - maxi;if (maxi >= remain) { // there will be always zero // or more element // which will not participate in making pairs ans = remain;} else{ // if n is odd then except one element // we can always form pair for every element // if n is even then all the elements can form pair ans = Math.floor(n / 2);}document.write(ans);freq.clear();// This code is contributed by gfgking.</script> |
Output
3
Time Complexity of this approach is O(N) since we are traversing through all the elements to form the frequency array.
Auxiliary Space is O(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!
