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>
Producción:
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>
Producción:
7
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)