Sum of absolute differences of indices of occurrences of each array element
Given an array arr[] consisting of N integers, the task for each array element arr[i] is to print the sum of |i β j| for all possible indices j such that arr[i] = arr[j].
Examples:
Input: arr[] = {1, 3, 1, 1, 2}
Output: 5 0 3 4 0
Explanation:
For arr[0], sum = |0 β 0| + |0 β 2| + |0 β 3| = 5.
For arr[1], sum = |1 β 1| = 0.
For arr[2], sum = |2 β 0| + |2 β 2| + |2 β 3| = 3.
For arr[3], sum = |3 β 0| + |3 β 2| + |3 β 3| = 4.
For arr[4], sum = |4 β 4| = 0.
Therefore, the required output is 5 0 3 4 0.Input: arr[] = {1, 1, 1}
Output: 3 2 3
Naive approach: The simplest approach is to traverse the given array and for each element arr[i] ( 0 ? i ? N ), traverse the array and check if arr[i] is same as arr[j] ( 0 ? j ? N ). If found to be true, add abs(i β j) to the sum print the sum obtained for each array element.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find sum of differences // of indices of occurrences of each // unique array element void sum( int arr[], int n) { // Traverse over the array for ( int i = 0; i < n; i++) { int sum = 0; // Check for every other elements of the array for ( int j = 0; j < n; j++) { // Add into sum if such pair found if (arr[i] == arr[j]) { sum += abs (i - j); } } // Print the sum cout << sum << " " ; } } // Driver Code int main() { // Given array int arr[] = { 1, 3, 1, 1, 2 }; // Given size int n = sizeof (arr) / sizeof (arr[0]); // Function call sum(arr, n); return 0; } |
Java
import java.util.Arrays; public class Main { // Function to find sum of differences // of indices of occurrences of each // unique array element public static void sum( int [] arr, int n) { // Traverse over the array for ( int i = 0 ; i < n; i++) { int sum = 0 ; // Check for every other elements of the array for ( int j = 0 ; j < n; j++) { // Add into sum if such pair found if (arr[i] == arr[j]) { sum += Math.abs(i - j); } } // Print the sum System.out.print(sum + " " ); } } // Driver Code public static void main(String[] args) { // Given array int [] arr = { 1 , 3 , 1 , 1 , 2 }; // Given size int n = arr.length; // Function call sum(arr, n); } } |
Python3
def sum (arr, n): # Traverse over the array for i in range (n): s = 0 # Check for every other elements of the array for j in range (n): # Add into sum if such pair found if arr[i] = = arr[j]: s + = abs (i - j) # Print the sum print (s, end = " " ) # Driver code if __name__ = = '__main__' : # Given array arr = [ 1 , 3 , 1 , 1 , 2 ] # Given size n = len (arr) # Function call sum (arr, n) |
Javascript
// JavaScript program for the above approach // Function to find sum of differences // of indices of occurrences of each // unique array element function sum(arr, n) { // Traverse over the array for (let i = 0; i < n; i++) { let sum = 0; // Check for every other elements of the array for (let j = 0; j < n; j++) { // Add into sum if such pair found if (arr[i] === arr[j]) { sum += Math.abs(i - j); } } // Print the sum console.log(sum + " " ); } } // Driver Code ( function main() { // Given array let arr = [1, 3, 1, 1, 2]; // Given size let n = arr.length; // Function call sum(arr, n); })(); |
C#
using System; public class GFG { // Function to find sum of differences // of indices of occurrences of each // unique array element public static void Sum( int [] arr, int n) { // Traverse over the array for ( int i = 0; i < n; i++) { int sum = 0; // Check for every other elements of the array for ( int j = 0; j < n; j++) { // Add into sum if such pair found if (arr[i] == arr[j]) { sum += Math.Abs(i - j); } } // Print the sum Console.Write(sum + " " ); } } public static void Main() { // Given array int [] arr = { 1, 3, 1, 1, 2 }; // Given size int n = arr.Length; // Function call Sum(arr, n); } } |
5 0 3 4 0
Time Complexity: O(N2) where N is the size of the given array.
Auxiliary Space: O(1)
Efficient Approach: The idea is to use Map data structure to optimize the above approach. Follow the steps below to solve the problem:
- Initialize a Map to store the vector of indices for repetitions of each unique element present in the array.
- Traverse the given array from i = 0 to N β 1 and for each array element arr[i], initialize the sum with 0 and traverse the vector map[arr[i]] which stores the indices of the occurrences of the element arr[i].
- For each value j present in the vector, increment the sum by abs(i β j).
- After traversing the vector, store the sum for the element at index i and print the sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find sum of differences // of indices of occurrences of each // unique array element void sum( int arr[], int n) { // Stores indices of each // array element map< int , vector< int > > mp; // Store the indices for ( int i = 0; i < n; i++) { mp[arr[i]].push_back(i); } // Stores the sums int ans[n]; // Traverse the array for ( int i = 0; i < n; i++) { // Find sum for each element int sum = 0; // Iterate over the Map for ( auto it : mp[arr[i]]) { // Calculate sum of // occurrences of arr[i] sum += abs (it - i); } // Store sum for // current element ans[i] = sum; } // Print answer for each element for ( int i = 0; i < n; i++) { cout << ans[i] << " " ; } return ; } // Driver Code int main() { // Given array int arr[] = { 1, 3, 1, 1, 2 }; // Given size int n = sizeof (arr) / sizeof (arr[0]); // Function call sum(arr, n); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find sum of differences // of indices of occurrences of each // unique array element static void sum( int arr[], int n) { // Stores indices of each // array element HashMap<Integer, Vector<Integer>> mp = new HashMap<>(); // Store the indices for ( int i = 0 ; i < n; i++) { Vector<Integer> v = new Vector<>(); v.add(i); if (mp.containsKey(arr[i])) v.addAll(mp.get(arr[i])); mp.put(arr[i], v); } // Stores the sums int []ans = new int [n]; // Traverse the array for ( int i = 0 ; i < n; i++) { // Find sum for each element int sum = 0 ; // Iterate over the Map for ( int it : mp.get(arr[i])) { // Calculate sum of // occurrences of arr[i] sum += Math.abs(it - i); } // Store sum for // current element ans[i] = sum; } // Print answer for each element for ( int i = 0 ; i < n; i++) { System.out.print(ans[i] + " " ); } return ; } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 1 , 3 , 1 , 1 , 2 }; // Given size int n = arr.length; // Function call sum(arr, n); } } // This code is contributed by Princi Singh |
Python3
# Python3 program for the above approach from collections import defaultdict # Function to find sum of differences # of indices of occurrences of each # unique array element def sum_i(arr, n): # Stores indices of each # array element mp = defaultdict( lambda : []) # Store the indices for i in range (n): mp[arr[i]].append(i) # Stores the sums ans = [ 0 ] * n # Traverse the array for i in range (n): # Find sum for each element sum = 0 # Iterate over the Map for it in mp[arr[i]]: # Calculate sum of # occurrences of arr[i] sum + = abs (it - i) # Store sum for # current element ans[i] = sum # Print answer for each element for i in range (n): print (ans[i], end = " " ) # Driver code if __name__ = = '__main__' : # Given array arr = [ 1 , 3 , 1 , 1 , 2 ] # Given size n = len (arr) # Function Call sum_i(arr, n) # This code is contributed by Shivam Singh |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find sum of differences // of indices of occurrences of each // unique array element static void sum( int []arr, int n) { // Stores indices of each // array element Dictionary< int , List< int >> mp = new Dictionary< int , List< int >>(); // Store the indices for ( int i = 0; i < n; i++) { List< int > v = new List< int >(); v.Add(i); if (mp.ContainsKey(arr[i])) v.AddRange(mp[arr[i]]); mp[arr[i]]= v; } // Stores the sums int []ans = new int [n]; // Traverse the array for ( int i = 0; i < n; i++) { // Find sum for each element int sum = 0; // Iterate over the Map foreach ( int it in mp[arr[i]]) { // Calculate sum of // occurrences of arr[i] sum += Math.Abs(it - i); } // Store sum for // current element ans[i] = sum; } // Print answer for each element for ( int i = 0; i < n; i++) { Console.Write(ans[i] + " " ); } return ; } // Driver Code public static void Main(String[] args) { // Given array int []arr = { 1, 3, 1, 1, 2 }; // Given size int n = arr.Length; // Function call sum(arr, n); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program for the above approach // Function to find sum of differences // of indices of occurrences of each // unique array element function sum(arr, n) { // Stores indices of each // array element var mp = new Map(); // Store the indices for ( var i = 0; i < n; i++) { if (mp.has(arr[i])) { var tmp = mp.get(arr[i]); tmp.push(i); mp.set(arr[i], tmp); } else { mp.set(arr[i], [i]); } } // Stores the sums var ans = Array(n); // Traverse the array for ( var i = 0; i < n; i++) { // Find sum for each element var sum = 0; // Iterate over the Map mp.get(arr[i]).forEach(it => { // Calculate sum of // occurrences of arr[i] sum += Math.abs(it - i); }); // Store sum for // current element ans[i] = sum; } // Print answer for each element for ( var i = 0; i < n; i++) { document.write( ans[i] + " " ); } return ; } // Driver Code // Given array var arr = [1, 3, 1, 1, 2]; // Given size var n = arr.length; // Function call sum(arr, n); </script> |
5 0 3 4 0
Time Complexity: O(N * L) where N is the size of the given array and L is the maximum frequency of any array element.
Auxiliary Space: O(N)