Given an array arr[] of length N containing array elements in the range [1, N], the task is to find the maximum number of pairs having equal sum, given that any element from the array can only be part of a single pair.
Examples:
Input: arr[] = {1, 4, 1, 4}
Output: 2
Explanation: Pairs {{1, 4}, {1, 4}} have equal sum 5.Input: arr[] = {1, 2, 4, 3, 3, 5, 6}
Output: 3
Explanation: Pairs {{1, 5}, {2, 4}, {3, 3}} have equal sum 6.
Approach:
The sum of a pair that can be obtained from the array can neither be less than 2 times the minimum element of the array nor greater than 2 times the largest element, thus we find the maximum number of pairs that can be obtained for each of the sums lying between these extremities and output the maximum among these.
The approach to implement this is as follows:
- Store the frequencies of all the elements of the given array.
- Iterate through every sum lying between the extremities and count the maximum number of pairs we can obtain for each of these sums.
- Print the maximum count among all such pairs obtained to be giving the same summations.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum count// of pairs having equal sumint maxCount(vector<int>& freq, int mini, int maxi){ // Size of the array int n = freq.size() - 1; int ans = 0; // Iterate through every sum of pairs // possible from the given array for (int sum = 2 * mini; sum <= 2 * maxi; ++sum) { // Count of pairs with given sum int possiblePair = 0; for (int firElement = 1; firElement < (sum + 1) / 2; firElement++) { // Check for a possible pair if (sum - firElement <= maxi) { // Update count of possible pair possiblePair += min(freq[firElement], freq[sum - firElement]); } } if (sum % 2 == 0) { possiblePair += freq[sum / 2] / 2; } // Update the answer by taking the // pair which is maximum // for every possible sum ans = max(ans, possiblePair); } // Return the max possible pair return ans;}// Function to return the// count of pairsint countofPairs(vector<int>& a){ // Size of the array int n = a.size(); int mini = *min_element(a.begin(), a.end()), maxi = *max_element(a.begin(), a.end()); // Stores the frequencies vector<int> freq(n + 1, 0); // Count the frequency for (int i = 0; i < n; ++i) freq[a[i]]++; return maxCount(freq, mini, maxi);}// Driver Codeint main(){ vector<int> a = { 1, 2, 4, 3, 3, 5, 6 }; // Function Call cout << countofPairs(a) << endl;} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG{// Function to find the maximum count// of pairs having equal sumstatic int maxCount(int[] freq,int maxi,int mini){ // Size of the array int n = freq.length - 1; int ans = 0; // Iterate through every sum of pairs // possible from the given array for(int sum = 2*mini; sum <= 2 * maxi; ++sum) { // Count of pairs with given sum int possiblePair = 0; for(int firElement = 1; firElement < (sum + 1) / 2; firElement++) { // Check for a possible pair if (sum - firElement <= maxi) { // Update count of possible pair possiblePair += Math.min(freq[firElement], freq[sum - firElement]); } } if (sum % 2 == 0) { possiblePair += freq[sum / 2] / 2; } // Update the answer by taking the // pair which is maximum // for every possible sum ans = Math.max(ans, possiblePair); } // Return the max possible pair return ans;}// Function to return the// count of pairsstatic int countofPairs(int[] a){ // Size of the array int n = a.length; // Stores the frequencies int []freq = new int[n + 1]; int maxi = -1; int mini = n+1; for(int i = 0;i<n;i++) { maxi = Math.max(maxi,a[i]); mini = Math.min(mini,a[i]); } // Count the frequency for(int i = 0; i < n; ++i) freq[a[i]]++; return maxCount(freq,maxi,mini);}// Driver Codepublic static void main(String[] args){ int []a = { 1, 2, 4, 3, 3, 5, 6 }; System.out.print(countofPairs(a) + "\n");}}// This code is contributed by Princi Singh |
Python3
# Python3 program to implement# the above approach# Function to find the maximum count# of pairs having equal sumdef maxCount(freq, maxi, mini): # Size of the array n = len(freq) - 1 ans = 0 # Iterate through every sum of pairs # possible from the given array sum = 2*mini while sum <= 2 * maxi: # Count of pairs with given sum possiblePair = 0 for firElement in range(1, (sum + 1) // 2): # Check for a possible pair if (sum - firElement <= maxi): # Update count of possible pair possiblePair += min(freq[firElement], freq[sum - firElement]) if (sum % 2 == 0): possiblePair += freq[sum // 2] // 2 sum += 1 # Update the answer by taking the # pair which is maximum # for every possible sum ans = max(ans, possiblePair) # Return the max possible pair return ans# Function to return the# count of pairsdef countofPairs(a): # Size of the array n = len(a) # Stores the frequencies freq = [0] * (n + 1) maxi = -1 mini = n+1 for i in range(len(a)): maxi = max(maxi, a[i]) mini = min(mini, a[i]) # Count the frequency for i in range(n): freq[a[i]] += 1 return maxCount(freq, maxi, mini)# Driver Codeif __name__ == "__main__": a = [1, 2, 4, 3, 3, 5, 6] print(countofPairs(a))# This code is contributed by chitranayal |
C#
// C# program to implement// the above approachusing System;class GFG { // Function to find the maximum count // of pairs having equal sum static int maxCount(int[] freq) { // Size of the array int n = freq.Length - 1; int ans = 0; // Iterate through every sum of pairs // possible from the given array for (int sum = 2; sum <= 2 * n; ++sum) { // Count of pairs with given sum int possiblePair = 0; for (int firElement = 1; firElement < (sum + 1) / 2; firElement++) { // Check for a possible pair if (sum - firElement <= n) { // Update count of possible pair possiblePair += Math.Min(freq[firElement], freq[sum - firElement]); } } if (sum % 2 == 0) { possiblePair += freq[sum / 2] / 2; } // Update the answer by taking the // pair which is maximum // for every possible sum ans = Math.Max(ans, possiblePair); } // Return the max possible pair return ans; } // Function to return the // count of pairs static int countofPairs(int[] a) { // Size of the array int n = a.Length; // Stores the frequencies int[] freq = new int[n + 1]; // Count the frequency for (int i = 0; i < n; ++i) freq[a[i]]++; return maxCount(freq); } // Driver Code public static void Main(String[] args) { int[] a = { 1, 2, 4, 3, 3, 5, 6 }; Console.Write(countofPairs(a) + "\n"); }}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program to implement// the above approach// Function to find the maximum count// of pairs having equal sumfunction maxCount(freq, maxi, mini){ // Size of the array let n = freq.length - 1; let ans = 0; // Iterate through every sum of pairs // possible from the given array for(let sum = 2*mini; sum <= 2 * maxi; ++sum) { // Count of pairs with given sum let possiblePair = 0; for(let firElement = 1; firElement < Math.floor((sum + 1) / 2); firElement++) { // Check for a possible pair if (sum - firElement <= maxi) { // Update count of possible pair possiblePair += Math.min(freq[firElement], freq[sum - firElement]); } } if (sum % 2 == 0) { possiblePair += freq[sum / 2] / 2; } // Update the answer by taking the // pair which is maximum // for every possible sum ans = Math.max(ans, possiblePair); } // Return the max possible pair return ans;} // Function to return the// count of pairsfunction countofPairs(a){ // Size of the array let n = a.length; // Stores the frequencies let freq = Array.from({length: n+1}, (_, i) => 0); let maxi = -1; let mini = n+1; for(let i = 0;i<n;i++) { maxi = Math.max(maxi,a[i]); mini = Math.min(mini,a[i]); } // Count the frequency for(let i = 0; i < n; ++i) freq[a[i]]++; return maxCount(freq,maxi,mini);}// Driver Code let a = [ 1, 2, 4, 3, 3, 5, 6 ]; document.write(countofPairs(a)); </script> |
Output
3
Time Complexity: O(N2)
Auxiliary Space: 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!
