Count of index pairs with equal elements in an array
AuxilGiven an array of n elements. The task is to count the total number of indices (i, j) such that arr[i] = arr[j] and i < j
Examples :
Input : arr[] = {1, 1, 2} Output : 1 As arr[0] = arr[1], the pair of indices is (0, 1) Input : arr[] = {1, 1, 1} Output : 3 As arr[0] = arr[1], the pair of indices is (0, 1), (0, 2) and (1, 2) Input : arr[] = {1, 2, 3} Output : 0
Method 1 (Brute Force): For each index i, find element after it with same value as arr[i]. Below is the implementation of this approach:
Implementation:
C++
// C++ program to count of pairs with equal // elements in an array. #include<bits/stdc++.h> using namespace std; // Return the number of pairs with equal // values. int countPairs( int arr[], int n) { int ans = 0; // for each index i and j for ( int i = 0; i < n; i++) for ( int j = i+1; j < n; j++) // finding the index with same // value but different index. if (arr[i] == arr[j]) ans++; return ans; } // Driven Program int main() { int arr[] = { 1, 1, 2 }; int n = sizeof (arr)/ sizeof (arr[0]); cout << countPairs(arr, n) << endl; return 0; } |
Java
// Java program to count of pairs with equal // elements in an array. class GFG { // Return the number of pairs with equal // values. static int countPairs( int arr[], int n) { int ans = 0 ; // for each index i and j for ( int i = 0 ; i < n; i++) for ( int j = i+ 1 ; j < n; j++) // finding the index with same // value but different index. if (arr[i] == arr[j]) ans++; return ans; } //driver code public static void main (String[] args) { int arr[] = { 1 , 1 , 2 }; int n = arr.length; System.out.println(countPairs(arr, n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to # count of pairs with equal # elements in an array. # Return the number of # pairs with equal values. def countPairs(arr, n): ans = 0 # for each index i and j for i in range ( 0 , n): for j in range (i + 1 , n): # finding the index # with same value but # different index. if (arr[i] = = arr[j]): ans + = 1 return ans # Driven Code arr = [ 1 , 1 , 2 ] n = len (arr) print (countPairs(arr, n)) # This code is contributed # by Smitha |
C#
// C# program to count of pairs with equal // elements in an array. using System; class GFG { // Return the number of pairs with equal // values. static int countPairs( int []arr, int n) { int ans = 0; // for each index i and j for ( int i = 0; i < n; i++) for ( int j = i+1; j < n; j++) // finding the index with same // value but different index. if (arr[i] == arr[j]) ans++; return ans; } // Driver code public static void Main () { int []arr = { 1, 1, 2 }; int n = arr.Length; Console.WriteLine(countPairs(arr, n)); } } // This code is contributed by anuj_67. |
PHP
<?php // PHP program to count of // pairs with equal elements // in an array. // Return the number of pairs // with equal values. function countPairs( $arr , $n ) { $ans = 0; // for each index i and j for ( $i = 0; $i < $n ; $i ++) for ( $j = $i + 1; $j < $n ; $j ++) // finding the index with same // value but different index. if ( $arr [ $i ] == $arr [ $j ]) $ans ++; return $ans ; } // Driven Code $arr = array ( 1, 1, 2 ); $n = count ( $arr ); echo countPairs( $arr , $n ) ; // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to count of pairs with equal // elements in an array. // Return the number of pairs with equal // values. function countPairs(arr, n) { let ans = 0; // for each index i and j for (let i = 0; i < n; i++) for (let j = i+1; j < n; j++) // finding the index with same // value but different index. if (arr[i] == arr[j]) ans++; return ans; } // Driver code let arr = [ 1, 1, 2 ]; let n = arr.length; document.write(countPairs(arr, n)); // This code is contributed by susmitakundugoaldanga. </script> |
1
Time Complexity : O(n2)
Auxiliary Space: O(1)
Method 2 (Efficient approach):
The idea is to count the frequency of each number and then find the number of pairs with equal elements. Suppose, a number x appears k times at index i1, i2,….,ik. Then pick any two indexes ix and iy which will be counted as 1 pair. Similarly, iy and ix can also be pair. So, choose nC2 is the number of pairs such that arr[i] = arr[j] = x.
Below is the implementation of this approach:
C++
// C++ program to count of index pairs with // equal elements in an array. #include<bits/stdc++.h> using namespace std; // Return the number of pairs with equal // values. int countPairs( int arr[], int n) { unordered_map< int , int > mp; // Finding frequency of each number. for ( int i = 0; i < n; i++) mp[arr[i]]++; // Calculating pairs of each value. int ans = 0; for ( auto it=mp.begin(); it!=mp.end(); it++) { int count = it->second; ans += (count * (count - 1))/2; } return ans; } // Driven Program int main() { int arr[] = {1, 1, 2}; int n = sizeof (arr)/ sizeof (arr[0]); cout << countPairs(arr, n) << endl; return 0; } |
Java
// Java program to count of index pairs with // equal elements in an array. import java.util.*; class GFG { public static int countPairs( int arr[], int n) { //A method to return number of pairs with // equal values HashMap<Integer,Integer> hm = new HashMap<>(); // Finding frequency of each number. for ( int i = 0 ; i < n; i++) { if (hm.containsKey(arr[i])) hm.put(arr[i],hm.get(arr[i]) + 1 ); else hm.put(arr[i], 1 ); } int ans= 0 ; // Calculating count of pairs with equal values for (Map.Entry<Integer,Integer> it : hm.entrySet()) { int count = it.getValue(); ans += (count * (count - 1 )) / 2 ; } return ans; } // Driver code public static void main(String[] args) { int arr[] = new int []{ 1 , 2 , 3 , 1 }; System.out.println(countPairs(arr,arr.length)); } } // This Code is Contributed // by Adarsh_Verma |
Python3
# Python3 program to count of index pairs # with equal elements in an array. import math as mt # Return the number of pairs with # equal values. def countPairs(arr, n): mp = dict () # Finding frequency of each number. for i in range (n): if arr[i] in mp.keys(): mp[arr[i]] + = 1 else : mp[arr[i]] = 1 # Calculating pairs of each value. ans = 0 for it in mp: count = mp[it] ans + = (count * (count - 1 )) / / 2 return ans # Driver Code arr = [ 1 , 1 , 2 ] n = len (arr) print (countPairs(arr, n)) # This code is contributed by mohit kumar 29 |
C#
// C# program to count of index pairs with // equal elements in an array. using System; using System.Collections.Generic; class GFG { // Return the number of pairs with // equal values. public static int countPairs( int []arr, int n) { // A method to return number of pairs // with equal values Dictionary< int , int > hm = new Dictionary< int , int >(); // Finding frequency of each number. for ( int i = 0; i < n; i++) { if (hm.ContainsKey(arr[i])) { int a = hm[arr[i]]; hm.Remove(arr[i]); hm.Add(arr[i], a + 1); } else hm.Add(arr[i], 1); } int ans = 0; // Calculating count of pairs with // equal values foreach ( var it in hm) { int count = it.Value; ans += (count * (count - 1)) / 2; } return ans; } // Driver code public static void Main() { int []arr = new int []{1, 2, 3, 1}; Console.WriteLine(countPairs(arr,arr.Length)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to count of index pairs with // equal elements in an array. function countPairs(arr,n) { //A method to return number of pairs with // equal values let hm = new Map(); // Finding frequency of each number. for (let i = 0; i < n; i++) { if (hm.has(arr[i])) hm.set(arr[i],hm.get(arr[i]) + 1); else hm.set(arr[i], 1); } let ans=0; // Calculating count of pairs with equal values for (let [key, value] of hm.entries()) { let count = value; ans += (count * (count - 1)) / 2; } return ans; } // Driver code let arr=[1, 2, 3, 1]; document.write(countPairs(arr,arr.length)); // This code is contributed by patel2127 </script> |
1
Time Complexity : O(n)
Auxiliary Space: O(n)