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 elementvoid 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 Codeint 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 codeif __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 elementfunction 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); }} |
Output
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 elementvoid 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 Codeint 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 approachimport java.util.*;class GFG{// Function to find sum of differences// of indices of occurrences of each// unique array elementstatic 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 Codepublic 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 elementdef 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 codeif __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 approachusing System;using System.Collections.Generic;class GFG{// Function to find sum of differences// of indices of occurrences of each// unique array elementstatic 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 Codepublic 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 elementfunction 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 arrayvar arr = [1, 3, 1, 1, 2];// Given sizevar n = arr.length;// Function callsum(arr, n);</script> |
Output:
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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!