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.
Implementation:-
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// required pairs for every array elementvoid countEqualElementPairs(int arr[], int N){ //Taking this loop to not consider element at index i for(int i=0;i<N;i++) { //count for excluding arr[i] int count=0; //Counting all pairs except arr[i] for(int j=0;j<N-1;j++) { if(j==i)continue; for(int k=j+1;k<N;k++) { //k point to i which we don't have to consider if(k==i) continue; if(arr[k]==arr[j])count++; } } cout<<count<<" "; }}// Driver codeint main(){ // Given array int arr[] = { 1, 1, 2, 1, 2 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); countEqualElementPairs(arr, N);} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { public static void countEqualElementPairs(int arr[], int N) { //Taking this loop to not consider element at index i for(int i=0;i<N;i++) { //count for excluding arr[i] int count=0; //Counting all pairs except arr[i] for(int j=0;j<N-1;j++) { if(j==i)continue; for(int k=j+1;k<N;k++) { //k point to i which we don't have to consider if(k==i) continue; if(arr[k]==arr[j])count++; } } System.out.print(count+" "); } } public static void main (String[] args) { //size of array int N = 5; //array int arr[]={1,1,2,1,2}; //calling function countEqualElementPairs(arr,N); }}//this code is contributed by shubhamrajput6156 |
Python3
# Function to count the number of required pairs for every array elementdef countEqualElementPairs(arr, N): # Taking this loop to not consider element at index i for i in range(N): # count for excluding arr[i] count = 0 # Counting all pairs except arr[i] for j in range(N-1): if j == i: continue for k in range(j+1, N): # k point to i which we don't have to consider if k == i: continue if arr[k] == arr[j]: count += 1 print(count, end=" ")# Driver codeif __name__ == '__main__': # Given array arr = [1, 1, 2, 1, 2] # Size of the array N = len(arr) countEqualElementPairs(arr, N) |
Javascript
// Function to count the number of// required pairs for every array elementfunction countEqualElementPairs(arr) { const N = arr.length; //Taking this loop to not consider element at index i for (let i = 0; i < N; i++) { //count for excluding arr[i] let count = 0; //Counting all pairs except arr[i] for (let j = 0; j < N - 1; j++) { if (j === i) continue; for (let k = j + 1; k < N; k++) { //k point to i which we don't have to consider if (k === i) continue; if (arr[k] === arr[j]) count++; } } console.log(count); }}// Driver codeconst arr = [1, 1, 2, 1, 2];countEqualElementPairs(arr); |
C#
// C# programusing System;class GFG { static void countEqualElementPairs(int[] arr, int N) { // Taking this loop to not consider element at index // i for (int i = 0; i < N; i++) { // count for excluding arr[i] int count = 0; // Counting all pairs except arr[i] for (int j = 0; j < N - 1; j++) { if (j == i) continue; for (int k = j + 1; k < N; k++) { // k point to i which we don't have to // consider if (k == i) continue; if (arr[k] == arr[j]) count++; } } Console.Write(count + " "); } } // Driver code public static void Main() { // Given array int[] arr = { 1, 1, 2, 1, 2 }; // Size of the array int N = arr.Length; countEqualElementPairs(arr, N); }} |
Output
2 2 3 2 3
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the observation that, for any ith 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 ith element such that their values are the same as the value of the ith element.
Follow the steps below to solve the problem:
- Initialize a map, say mp, to store the frequency of every array element.
- Traverse the map to count the number of pairs made up of equal values. Store the count in a variable, say total.
- Traverse the array and for every ith index, print total – (mp[arr[i]] – 1) as the required answer.
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// required pairs for every array elementvoid countEqualElementPairs(int arr[], int N){ // Initialize a map unordered_map<int, int> mp; // Update the frequency // of every element for (int i = 0; i < N; i++) { mp[arr[i]] += 1; } // Stores the count of pairs int total = 0; // Traverse the map for (auto i : mp) { // Count the number of ways to // select pairs consisting of // equal elements only total += (i.second * (i.second - 1)) / 2; } // Traverse the array for (int i = 0; i < N; i++) { // Print the count for // every array element cout << total - (mp[arr[i]] - 1) << " "; }}// Driver codeint main(){ // Given array int arr[] = { 1, 1, 2, 1, 2 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); countEqualElementPairs(arr, N);} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.Map;import java.util.HashMap;class GFG{ // Function to count the number of // required pairs for every array element public static void countEqualElementPairs(int arr[], int N) { // Initialize a map HashMap<Integer, Integer> map = new HashMap<>(); // Update the frequency // of every element for (int i = 0; i < N; i++) { Integer k = map.get(arr[i]); map.put(arr[i], (k == null) ? 1 : k + 1); } // Stores the count of pairs int total = 0; // Traverse the map for (Map.Entry<Integer, Integer> e : map.entrySet()) { // Count the number of ways to // select pairs consisting of // equal elements only total += (e.getValue() * (e.getValue() - 1)) / 2; } // Traverse the array for (int i = 0; i < N; i++) { // Print the count for // every array element System.out.print(total - (map.get(arr[i]) - 1) + " "); } } // Driver code public static void main(String[] args) { // Given array int arr[] = { 1, 1, 2, 1, 2 }; // Size of the array int N = 5; countEqualElementPairs(arr, N); }}// This code is contributed by adity7409. |
Python3
# Python3 program for the above approach# Function to count the number of# required pairs for every array elementdef countEqualElementPairs(arr, N): # Initialize a map mp = {} # Update the frequency # of every element for i in range(N): if arr[i] in mp: mp[arr[i]] += 1 else: mp[arr[i]] = 1 # Stores the count of pairs total = 0 # Traverse the map for key,value in mp.items(): # Count the number of ways to # select pairs consisting of # equal elements only total += (value * (value - 1)) / 2 # Traverse the array for i in range(N): # Print the count for # every array element print(int(total - (mp[arr[i]] - 1)),end = " ")# Driver codeif __name__ == '__main__': # Given array arr = [1, 1, 2, 1, 2] # Size of the array N = len(arr) countEqualElementPairs(arr, N) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to count the number of// required pairs for every array elementstatic void countEqualElementPairs(int[] arr, int N){ // Initialize a map Dictionary<int, int> map = new Dictionary<int, int>(); // Update the frequency // of every element for(int i = 0; i < N; i++) { if (!map.ContainsKey(arr[i])) map[arr[i]] = 1; else map[arr[i]]++; } // Stores the count of pairs int total = 0; // Traverse the map foreach(KeyValuePair<int, int> e in map) { // Count the number of ways to // select pairs consisting of // equal elements only total += (e.Value * (e.Value - 1)) / 2; } // Traverse the array for(int i = 0; i < N; i++) { // Print the count for // every array element Console.Write(total - (map[arr[i]] - 1) + " "); }}// Driver codepublic static void Main(){ // Given array int[] arr = { 1, 1, 2, 1, 2 }; // Size of the array int N = 5; countEqualElementPairs(arr, N);}}// This code is contributed by ukasp |
Javascript
<script>// Javascript program for the above approach// Function to count the number of// required pairs for every array elementfunction countEqualElementPairs(arr, N){ // Initialize a map var mp = new Map(); // Update the frequency // of every element for(var i = 0; i < N; i++) { if (mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i]) + 1); } else { mp.set(arr[i], 1); } } // Stores the count of pairs var total = 0; // Traverse the map mp.forEach((value, key) => { // Count the number of ways to // select pairs consisting of // equal elements only total += (value * (value - 1)) / 2; }); // Traverse the array for(var i = 0; i < N; i++) { // Print the count for // every array element document.write(total - (mp.get(arr[i]) - 1) + " "); }}// Driver code// Given arrayvar arr = [ 1, 1, 2, 1, 2 ];// Size of the arrayvar N = arr.length;countEqualElementPairs(arr, N);// This code is contributed by rutvik_56</script> |
Output:
2 2 3 2 3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
