Count pairs of equal elements in an array

Given an array A[], the task is to find the number of pairs in the array in which A[i] is equal to A[j] and i<j.

Examples :

Input : A[] =  {4,3,3,4,4,1,1}
Output : 5
There are 5 pairs in which A[i] is equal to A[j] and i<j 
{0,3},{0,4},{3,4},{1,2} and {5,6}

Input : A[] =  {5,5,5,5,5}
Output : 10

Naive Approach :

The easiest way to solve this by using two loops. We create a count variable first. Then we iterate through every possible pair and if it satisfies the condition then we increment the count by 1. In the end, we return the count as our answer.

Implementation :

//Number of pairs in the array
//in which A[i] is equal to A[j] and i<j
#include<bits/stdc++.h>
using namespace std;
//C++ function to find the
//number of pairs in the array
//in which A[i] is equal to A[j] and i<j
int numpairs(int A[], int n) {
        int count=0;
        for(int i=0; i<n-1; i++)
        {
                 for(int j=i+1; j<n; j++)
                 {
                     if(A[i]==A[j])
                         count++;
                 }
     }
        return count;
    }
    //driver code
    int main() 
    { 
        int arr[] = {4,3,3,4,4,1,1}; 
        int  n = sizeof(arr) / sizeof(arr[0]); 
        printf("%d", numpairs(arr, n)) ; 
        return 0; 
    } 

Efficient Approach :

The efficient way is to use hashing. We will use a hash table to keep the count of occurrences of the element in the array.

We will also keep a count variable to get the number of pairs. We run a loop through the hashtable, and whenever we find the occurrence count greater than 1, we increment the count by the value of (occurence*(occurrence-1))/2 to get the total number of pairs formed by that element. For example, in the array {4,3,3,4,4,1,1}, 4 appears thrice so the count will get incremented by (3*2)/2 = 3,three pairs which are{0,3},{0,4} and {3,4}.

This way we will continue and in the end return the count as our answer.

//Number of pairs in the array
//in which A[i] is equal to A[j] and i<j
#include<bits/stdc++.h>
using namespace std;
//C++ function to find the
//number of pairs in the array
//in which A[i] is equal to A[j] and i<j
int numpairs(vector<int>& A) {
    unordered_map<int,int> mp;
    int count = 0;
    for(auto i:A)
    {
        mp[i]++;
    }
    for(auto i:mp)
    {
        if(i.second>1)
        {
            count += ((i.second*(i.second-1))/2);
        }
    }
    return count;
    }
    //driver code
    int main() 
    { 
        vector<int>arr = {4,3,3,4,4,1,1}; 
        printf("%d", numpairs(arr)) ; 
        return 0; 
    }