Count unordered pairs of equal elements for all subarrays | C ++ program for the above approach ; Function to count all pairs ( i , j ) such that arr [ i ] equals arr [ j ] in all possible subarrays of the array ; Stores the size of the array ; Stores the positions of all the distinct elements ; Append index corresponding to arr [ i ] in the map ; Traverse the map M ; Traverse the array ; Update the value of ans ; Update the value of the sum ; Print the value of ans ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void countPairs ( vector < int > arr ) { int N = arr . size ( ) ; int ans = 0 ; map < int , vector < int > > M ; for ( int i = 0 ; i < arr . size ( ) ; i ++ ) { M [ arr [ i ] ] . push_back ( i ) ; } for ( auto it : M ) { vector < int > v = it . second ; int sum = 0 ; for ( int j = 0 ; j < v . size ( ) ; j ++ ) { ans += sum * ( N - v [ j ] ) ; sum += v [ j ] + 1 ; } } cout << ans ; } int main ( ) { vector < int > arr = { 1 , 2 , 1 , 1 } ; countPairs ( arr ) ; return 0 ; }