Sum of absolute differences of indices of occurrences of each array element | Set 2 | C ++ program for the above approach ; Stores the count of occurrences and previous index of every element ; Constructor ; Function to calculate the sum of absolute differences of indices of occurrences of array element ; Stores the count of elements and their previous indices ; Initialize 2 arrays left [ ] and right [ ] of size N ; Traverse the given array ; If arr [ i ] is present in the Map ; Update left [ i ] to 0 and update the value of arr [ i ] in map ; Otherwise , get the value from the map and update left [ i ] ; Clear the map to calculate right [ ] array ; Traverse the array arr [ ] in reverse ; If arr [ i ] is present in theMap ; Update right [ i ] to 0 and update the value of arr [ i ] in the Map ; Otherwise get the value from the map and update right [ i ] ; Iterate in the range [ 0 , N - 1 ] and print the sum of left [ i ] and right [ i ] as the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct pairr { int count , prevIndex ; pairr ( int countt , int prevIndexx ) { count = countt ; prevIndex = prevIndexx ; } } ; void findSum ( int arr [ ] , int n ) { map < int , pairr * > mapp ; int left [ n ] ; int right [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { if ( mapp . find ( arr [ i ] ) == mapp . end ( ) ) { left [ i ] = 0 ; mapp [ arr [ i ] ] = new pairr ( 1 , i ) ; } else { pairr * tmp = mapp [ arr [ i ] ] ; left [ i ] = ( tmp -> count ) * ( i - tmp -> prevIndex ) + left [ tmp -> prevIndex ] ; mapp [ arr [ i ] ] = new pairr ( tmp -> count + 1 , i ) ; } } mapp . clear ( ) ; for ( int i = n - 1 ; i >= 0 ; i -- ) { if ( mapp . find ( arr [ i ] ) == mapp . end ( ) ) { right [ i ] = 0 ; mapp [ arr [ i ] ] = new pairr ( 1 , i ) ; } else { pairr * tmp = mapp [ arr [ i ] ] ; right [ i ] = ( tmp -> count ) * ( abs ( i - tmp -> prevIndex ) ) + right [ tmp -> prevIndex ] ; mapp [ arr [ i ] ] = new pairr ( tmp -> count + 1 , i ) ; } } for ( int i = 0 ; i < n ; i ++ ) cout << left [ i ] + right [ i ] << " ▁ " ; } int main ( ) { int arr [ ] = { 1 , 3 , 1 , 1 , 2 } ; int N = 5 ; findSum ( arr , N ) ; }