Count pairs of equal elements possible by excluding each array element once

Given an array arr[] of N integers, the task for each array element is to find the number of ways of choosing a pair of two equal elements excluding the current element.

Examples:

Input: arr[] = {1, 1, 2, 1, 2}
Output: 2 2 3 2 3
Explanation: 
For arr[0] (= 1): The remaining array elements are {1, 2, 1, 2}. Possible choice of pairs are (1, 1), (2, 2). Therefore, count is 2.
For arr[1] (= 1): The remaining array elements are {1, 2, 1, 2}. Therefore, count is 2.
For arr[2] (= 2): The remaining array elements are {1, 1, 1, 2}. Possible choice of pairs are (arr[0], arr[1]), (arr[1], arr[2]) and (arr[0], arr[2]). Therefore, count is 3.
For arr[3] (= 1): The remaining elements are {1, 1, 2, 2}. Therefore, count is 2.
For arr[4] (= 2): The remaining elements are {1, 1, 2, 1}. Therefore, count is 3.

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

Naive Approach: The simplest approach to solve this problem is to traverse the array for each array element, count all possible pairs of equal elements from the remaining array.
Time Complexity: O(N³)  
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized based on the observation that, for any i^th index (1 ≤ i ≤ N), calculate the following two values:

• The number of ways to choose two distinct elements having equal values from the array.
• The number of ways to choose an element from the N − 1 array elements other than the i^th element such that their values are the same as the value of the i^th element.

Follow the steps below to solve the problem:

1. Initialize a map, say mp, to store the frequency of every array element.
2. Traverse the map to count the number of pairs made up of equal values. Store the count in a variable, say total.
3. Traverse the array and for every i^th index, print total – (mp[arr[i]] – 1) as the required answer.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    void countEqualElementPairs(int arr[], int N) {          unordered_map<int, int> mp;                  for (int i = 0; i < N; i++) {         mp[arr[i]] += 1;     }             int total = 0;             for (auto i : mp) {                                       total += (i.second * (i.second - 1)) / 2;     }             for (int i = 0; i < N; i++) {                              cout << total - (mp[arr[i]] - 1)              << " ";     } }    int main() {          int arr[] = { 1, 1, 2, 1, 2 };             int N = sizeof(arr) / sizeof(arr[0]);        countEqualElementPairs(arr, N); }

Output:

2 2 3 2 3

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

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)