Dada una array arr[] de longitud N que contiene elementos de array en el rango [1, N] , la tarea es encontrar el número máximo de pares que tengan la misma suma, dado que cualquier elemento de la array solo puede ser parte de un solo par .
Ejemplos:
Entrada: arr[] = {1, 4, 1, 4}
Salida: 2
Explicación: Los pares {{1, 4}, {1, 4}} tienen igual suma 5.Entrada: arr[] = {1, 2, 4, 3, 3, 5, 6}
Salida: 3
Explicación: Los pares {{1, 5}, {2, 4}, {3, 3}} tienen igual suma 6 .
Acercarse:
La suma de un par que se puede obtener del arreglo no puede ser menor a 2 veces el elemento mínimo del arreglo ni mayor a 2 veces el elemento mayor, así encontramos el número máximo de pares que se pueden obtener para cada uno de los sumas que se encuentran entre estos extremos y salida el máximo entre estos.
El enfoque para implementar esto es el siguiente:
- Almacene las frecuencias de todos los elementos de la array dada.
- Iterar a través de cada suma que se encuentra entre los extremos y contar el número máximo de pares que podemos obtener para cada una de estas sumas.
- Imprime el conteo máximo entre todos esos pares obtenidos para dar las mismas sumas.
A continuación se muestra la implementación del enfoque anterior:
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 sum
int 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 pairs
int 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 Code
int main()
{
vector<int> a = { 1, 2, 4, 3, 3, 5, 6 };
// Function Call
cout << countofPairs(a) << endl;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function to find the maximum count
// of pairs having equal sum
static 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 pairs
static 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 Code
public 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 sum def 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 pairs def 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 Code if __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 approach
using 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 sum
function 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 pairs
function 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>
Producción
3
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)