Sum of absolute differences of indices of occurrences of each array element | Set 2 | 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
class pair : NEW_LINE INDENT def __init__ ( self , count , prevIndex ) : NEW_LINE INDENT self . count = count ; NEW_LINE self . prevIndex = prevIndex ; NEW_LINE DEDENT DEDENT def findSum ( arr , n ) : NEW_LINE INDENT map = { } ; NEW_LINE left = [ 0 for i in range ( n ) ] ; NEW_LINE right = [ 0 for i in range ( n ) ] ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] not in map ) : NEW_LINE INDENT left [ i ] = 0 ; NEW_LINE map [ arr [ i ] ] = pair ( 1 , i ) ; NEW_LINE DEDENT else : NEW_LINE INDENT tmp = map [ arr [ i ] ] ; NEW_LINE left [ i ] = ( tmp . count ) * ( i - tmp . prevIndex ) + left [ tmp . prevIndex ] NEW_LINE map [ arr [ i ] ] = pair ( tmp . count + 1 , i ) ; NEW_LINE DEDENT DEDENT map . clear ( ) ; NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( arr [ i ] not in map ) : NEW_LINE INDENT right [ i ] = 0 ; NEW_LINE map [ arr [ i ] ] = pair ( 1 , i ) ; NEW_LINE DEDENT else : NEW_LINE INDENT tmp = map [ arr [ i ] ] ; NEW_LINE right [ i ] = ( tmp . count ) * ( abs ( i - tmp . prevIndex ) ) + right [ tmp . prevIndex ] ; NEW_LINE map [ arr [ i ] ] = pair ( tmp . count + 1 , i ) ; NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT print ( left [ i ] + right [ i ] , end = " ▁ " ) ; NEW_LINE DEDENT DEDENT arr = [ 1 , 3 , 1 , 1 , 2 ] ; NEW_LINE N = len ( arr ) ; NEW_LINE findSum ( arr , N ) ; NEW_LINE