Dada una array arr[] que consta de N enteros, la tarea es contar el número de pares distintos (arr[i], arr[j]) en la array de modo que el promedio de pares también esté presente en la array .
Nota: Considere (arr[i], arr[j]) y (arr[j], arr[i]) como los mismos pares.
Ejemplos:
Entrada: arr[] = {2, 1, 3}
Salida: 1
Explicación: El único par cuyo promedio está presente en la array dada es (1, 3) (Promedio = 2).Entrada: arr[] = {4, 2, 5, 1, 3, 5}
Salida: 7
Enfoque ingenuo: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos contar como 0 para almacenar todo el recuento de pares cuyo promedio existe en la array.
- Inserta todos los elementos de la array en un conjunto S .
- Recorra el conjunto S y para cada elemento del conjunto S , genere todos los pares posibles de la array dada y si la suma de cualquier par es igual al elemento actual del conjunto , incremente el valor de count en 1 .
- Después de completar los pasos anteriores, imprima el valor de conteo como el conteo resultante de pares.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the number of // pairs from the array having sum S int getCountPairs(vector<int> arr, int N, int S) { // Stores the total count of // pairs whose sum is 2*S int count = 0; // Generate all possible pairs // and check their sums for(int i = 0; i < arr.size(); i++) { for(int j = i + 1; j < arr.size(); j++) { // If the sum is S, then // increment the count if ((arr[i] + arr[j]) == S) count++; } } // Return the total // count of pairs return count; } // Function to count of pairs having // whose average exists in the array int countPairs(vector<int> arr, int N) { // Initialize the count int count = 0; // Use set to remove duplicates unordered_set<int> S; // Add elements in the set for(int i = 0; i < N; i++) S.insert(arr[i]); for(int ele : S) { int sum = 2 * ele; // For every sum, count // all possible pairs count += getCountPairs(arr, N, sum); } // Return the total count return count; } // Driver Code int main() { vector<int> arr = { 4, 2, 5, 1, 3, 5 }; int N = arr.size(); cout << countPairs(arr, N); return 0; } // This code is contributed by Kingash
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to count the number of // pairs from the array having sum S public static int getCountPairs( int arr[], int N, int S) { // Stores the total count of // pairs whose sum is 2*S int count = 0; // Generate all possible pairs // and check their sums for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) { // If the sum is S, then // increment the count if ((arr[i] + arr[j]) == S) count++; } } // Return the total // count of pairs return count; } // Function to count of pairs having // whose average exists in the array public static int countPairs( int arr[], int N) { // Initialize the count int count = 0; // Use set to remove duplicates HashSet<Integer> S = new HashSet<>(); // Add elements in the set for (int i = 0; i < N; i++) S.add(arr[i]); for (int ele : S) { int sum = 2 * ele; // For every sum, count // all possible pairs count += getCountPairs( arr, N, sum); } // Return the total count return count; } // Driver Code public static void main(String[] args) { int arr[] = { 4, 2, 5, 1, 3, 5 }; int N = arr.length; System.out.print( countPairs(arr, N)); } }
Python3
# Python3 program for the above approach # Function to count the number of # pairs from the array having sum S def getCountPairs(arr, N, S): # Stores the total count of # pairs whose sum is 2*S count = 0 # Generate all possible pairs # and check their sums for i in range(len(arr)): for j in range(i + 1, len(arr)): # If the sum is S, then # increment the count if ((arr[i] + arr[j]) == S): count += 1 # Return the total # count of pairs return count # Function to count of pairs having # whose average exists in the array def countPairs(arr, N): # Initialize the count count = 0 # Use set to remove duplicates S = set([]) # Add elements in the set for i in range(N): S.add(arr[i]) for ele in S: sum = 2 * ele # For every sum, count # all possible pairs count += getCountPairs(arr, N, sum) # Return the total count return count # Driver Code if __name__ == "__main__": arr = [ 4, 2, 5, 1, 3, 5 ] N = len(arr) print(countPairs(arr, N)) # This code is contributed by ukasp
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to count the number of // pairs from the array having sum S public static int getCountPairs( int []arr, int N, int S) { // Stores the total count of // pairs whose sum is 2*S int count = 0; // Generate all possible pairs // and check their sums for (int i = 0; i < arr.Length; i++) { for (int j = i + 1; j < arr.Length; j++) { // If the sum is S, then // increment the count if ((arr[i] + arr[j]) == S) count++; } } // Return the total // count of pairs return count; } // Function to count of pairs having // whose average exists in the array public static int countPairs( int []arr, int N) { // Initialize the count int count = 0; // Use set to remove duplicates HashSet<int> S = new HashSet<int>(); // Add elements in the set for (int i = 0; i < N; i++) S.Add(arr[i]); foreach (int ele in S) { int sum = 2 * ele; // For every sum, count // all possible pairs count += getCountPairs( arr, N, sum); } // Return the total count return count; } // Driver Code public static void Main(String[] args) { int []arr = { 4, 2, 5, 1, 3, 5 }; int N = arr.Length; Console.Write( countPairs(arr, N)); } } // This code is contributed by Princi Singh
Javascript
<script> // JavaScript program for the above approach // Function to count the number of // pairs from the array having sum S function getCountPairs( arr, N, S) { // Stores the total count of // pairs whose sum is 2*S let count = 0; // Generate all possible pairs // and check their sums for (let i = 0; i < arr.length; i++) { for (let j = i + 1; j < arr.length; j++) { // If the sum is S, then // increment the count if ((arr[i] + arr[j]) == S) count++; } } // Return the total // count of pairs return count; } // Function to count of pairs having // whose average exists in the array function countPairs(arr, N) { // Initialize the count let count = 0; // Use set to remove duplicates let S = []; // Add elements in the set for (let i = 0; i < N; i++) S.push(arr[i]); for (let ele in S) { let sum = 2 * ele; // For every sum, count // all possible pairs count += getCountPairs( arr, N, sum); } // Return the total count return count; } // Driver code let arr = [ 4, 2, 5, 1, 3, 5 ]; let N = arr.length; document.write( countPairs(arr, N)); // This code is contributed by code_hunt. </script>
7
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar almacenando la frecuencia de la suma de todos los pares posibles en la array dada en un HashMap y encontrar el recuento de cada elemento de la array en consecuencia. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos contar como 0 para almacenar todo el recuento de pares cuyo promedio existe en la array.
- Inserta todos los elementos de la array en un conjunto S .
- Inicialice un HashMap, digamos M que almacena la frecuencia de la suma de todos los pares posibles en la array dada .
- Recorra el conjunto S y para cada elemento (digamos X ) en el conjunto S actualice el valor de cuenta por el valor (M[X]/2) .
- Después de completar los pasos anteriores, imprima el valor de conteo como el conteo resultante de pares.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for the above approach #include<bits/stdc++.h> using namespace std; // Function to count the total count // of pairs having sum S int getCountPairs(int arr[], int N, int S) { map<int,int> mp; // Store the total count of all // elements in map mp for (int i = 0; i < N; i++) { mp[arr[i]]++; } // Stores the total count of // total pairs int twice_count = 0; // Iterate through each element // and increment the count for (int i = 0; i < N; i++) { // If the value (S - arr[i]) // exists in the map hm if (mp.find(S - arr[i]) != mp.end()) { // Update the twice count twice_count += mp[S - arr[i]]; } if (S - arr[i] == arr[i]) twice_count--; } // Return the half of twice_count return twice_count / 2; } // Function to count of pairs having // whose average exists in the array int countPairs( int arr[], int N) { // Stores the total count of // pairs int count = 0; // Use set to remove duplicates set<int> S; // Insert all the element in // the set S for (int i = 0; i < N; i++) S.insert(arr[i]); for (int ele : S) { int sum = 2 * ele; // For every sum find the // getCountPairs count += getCountPairs( arr, N, sum); } // Return the total count of // pairs return count; } // Driver Code int main() { int N = 6; int arr[] = { 4, 2, 5, 1, 3, 5 }; cout<<(countPairs(arr, N)); } // This code is contributed by ipg2016107.
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to count the total count // of pairs having sum S static int getCountPairs(int arr[], int N, int S) { HashMap<Integer, Integer> mp = new HashMap<>(); // Store the total count of all // elements in map mp for (int i = 0; i < N; i++) { // Initialize value to 0, // if key not found if (!mp.containsKey(arr[i])) mp.put(arr[i], 0); mp.put(arr[i], mp.get(arr[i]) + 1); } // Stores the total count of // total pairs int twice_count = 0; // Iterate through each element // and increment the count for (int i = 0; i < N; i++) { // If the value (S - arr[i]) // exists in the map hm if (mp.get(S - arr[i]) != null) { // Update the twice count twice_count += mp.get( S - arr[i]); } if (S - arr[i] == arr[i]) twice_count--; } // Return the half of twice_count return twice_count / 2; } // Function to count of pairs having // whose average exists in the array public static int countPairs( int arr[], int N) { // Stores the total count of // pairs int count = 0; // Use set to remove duplicates HashSet<Integer> S = new HashSet<>(); // Insert all the element in // the set S for (int i = 0; i < N; i++) S.add(arr[i]); for (int ele : S) { int sum = 2 * ele; // For every sum find the // getCountPairs count += getCountPairs( arr, N, sum); } // Return the total count of // pairs return count; } // Driver Code public static void main(String[] args) { int N = 6; int arr[] = { 4, 2, 5, 1, 3, 5 }; System.out.println( countPairs(arr, N)); } }
Python3
# Python program for the above approach # Function to count the total count # of pairs having sum S def getCountPairs(arr,N,S): mp = {} # Store the total count of all # elements in map mp for i in range(N): # Initialize value to 0, # if key not found if (arr[i] not in mp): mp[arr[i]] = 0 mp[arr[i]] += 1 # Stores the total count of # total pairs twice_count = 0 # Iterate through each element # and increment the count for i in range(N): # If the value (S - arr[i]) # exists in the map hm if ((S - arr[i]) in mp): # Update the twice count twice_count += mp[S - arr[i]] if (S - arr[i] == arr[i]): twice_count -= 1 # Return the half of twice_count return (twice_count // 2) # Function to count of pairs having # whose average exists in the array def countPairs(arr,N): # Stores the total count of # pairs count = 0 # Use set to remove duplicates S = set() # Insert all the element in # the set S for i in range(N): S.add(arr[i]) for ele in S: sum = 2 * ele # For every sum find the # getCountPairs count += getCountPairs(arr, N, sum) # Return the total count of # pairs return count # Driver Code N = 6 arr = [4, 2, 5, 1, 3, 5 ] print(countPairs(arr, N)) # This code is contributed by shinjanpatra
Javascript
<script> // JavaScript program for the above approach // Function to count the total count // of pairs having sum S function getCountPairs(arr,N,S) { let mp = new Map(); // Store the total count of all // elements in map mp for (let i = 0; i < N; i++) { // Initialize value to 0, // if key not found if (!mp.has(arr[i])) mp.set(arr[i], 0); mp.set(arr[i], mp.get(arr[i]) + 1); } // Stores the total count of // total pairs let twice_count = 0; // Iterate through each element // and increment the count for (let i = 0; i < N; i++) { // If the value (S - arr[i]) // exists in the map hm if (mp.get(S - arr[i]) != null) { // Update the twice count twice_count += mp.get( S - arr[i]); } if (S - arr[i] == arr[i]) twice_count--; } // Return the half of twice_count return Math.floor(twice_count / 2); } // Function to count of pairs having // whose average exists in the array function countPairs(arr,N) { // Stores the total count of // pairs let count = 0; // Use set to remove duplicates let S = new Set(); // Insert all the element in // the set S for (let i = 0; i < N; i++) S.add(arr[i]); for (let ele of S.values()) { let sum = 2 * ele; // For every sum find the // getCountPairs count += getCountPairs( arr, N, sum); } // Return the total count of // pairs return count; } // Driver Code let N = 6; let arr=[4, 2, 5, 1, 3, 5 ]; document.write(countPairs(arr, N)); // This code is contributed by avanitrachhadiya2155 </script>
7
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)