Numbers of pairs from an array whose average is also present in the array

0 0 12 minutes read

Given an array arr[] consisting of N integers, the task is to count the number of distinct pairs (arr[i], arr[j]) in the array such that the average of pairs is also present in the array.
Note: Consider (arr[i], arr[j]) and (arr[j], arr[i]) as the same pairs.

Examples:

Input: arr[] = {2, 1, 3}
Output: 1
Explanation: The only one pair whose average is present in the given array is (1, 3) (Average = 2).

Input: arr[] = {4, 2, 5, 1, 3, 5}
Output: 7

Naive Approach: Follow the steps below to solve the problem:

Initialize a variable, say count as 0 to store all the count of pairs whose average exists in the array.
Insert all the array elements in an set S.
Traverse over the set S and for every element in the set S, generate all possible pairs of the given array and if the sum of any pairs is same as the current element in the set then increment the value of count by 1.
After completing the above steps, print the value of count as the resultant count of pairs.

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 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>

Output:

Time Complexity: O(N³)
Auxiliary Space: O(N)

Efficient Approach: The above approach can also be optimized by storing the frequency of the sum of all possible pairs in the given array in a HashMap and find the count for each element of the array accordingly. Follow the steps below to solve the problem:

Initialize a variable, say count as 0 to store all the count of pairs whose average exists in the array.
Insert all the array elements in an set S.
Initialize a HashMap, say M that stores the frequency of the sum of all possible pairs in the given array.
Traverse over the set S and for every element(say X) in the set S update the value of count by the value (M[X]/2).
After completing the above steps, print the value of count as the resultant count of pairs.

Below is the implementation of the above approach:

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

C#

using System;
using System.Collections.Generic;
 
class GFG
{
  // Function to count the total count
  // of pairs having sum S
  static int GetCountPairs(int[] arr, int N, int S)
  {
    Dictionary<int, int> mp = new Dictionary<int, int>();
 
    // 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[arr[i]] = 0;
 
      mp[arr[i]] = mp[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.ContainsKey(S - arr[i]))
      {
        // 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
  public static int CountPairs(int[] arr, int N)
  {
    // Stores the total count of
    // pairs
    int count = 0;
 
    // Use set to remove duplicates
    HashSet<int> S = new HashSet<int>();
 
    // Insert all the element in
    // the set S
    for (int i = 0; i < N; i++)
      S.Add(arr[i]);
 
    foreach (int ele in 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 };
    Console.WriteLine(
      CountPairs(arr, N));
  }
}
 
// This code is contributed by phasing17.

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>

Output:

Time Complexity: O(N²)
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 zambiatek!