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: Please refer to the previous post of this article for the simplest approach to solve the problem.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Map-based Approach: Please refer to the previous post of this article to solve the problem using Map.
Time Complexity: O(N*L)
Auxiliary Space: O(N)
Efficient Approach: The above approach can also be optimized by storing the previous index and the count of occurrences of every element in a HashMap. Follow the steps below to solve the problem:
- Initialize a HashMap, say M to store arr[i] as key and (count, previous index) as value.
- Initialize two arrays L[] and R[] of size N where L[i] denotes the sum of |i – j| for all possible indices j < i and arr[i] = arr[j] and R[i] denotes the sum of |i – j| for all possible indices j > i and arr[i] = arr[j].
- Traverse the given array arr[] over the range [0, N – 1] and perform the following steps:
- If arr[i] is present in the map M, then update the value of L[i] to 0 and M[arr[i]] to store pair {1, i} where the first element denotes the count of occurrences and the second element denotes the previous index of the element.
- Otherwise, find the value of arr[i] from the map M, and store the count and previous index in variables cnt and j respectively.
- Update the value of L[i] to (cnt * (i – j) + L[j]) and the value of arr[i] in M to store pair (cnt + 1, i).
- Repeat the same process to update the values in the array R[].
- Iterate over the range [0, N – 1] using the variable i and print the value (L[i] + R[i]) as the result.
Below is the implementation of the above approach:
C++
#include <cmath>#include <iostream>#include <map>using namespace std;// Function to calculate the sum of// absolute differences of indices// of occurrences of array elementvoid findSum(int arr[], int n){ // Stores the count of elements // and their previous indices map<int, pair<int, int> > map; // Initialize 2 arrays left[] // and right[] of size N int left[n], right[n]; // Traverse the given array for (int i = 0; i < n; i++) { // If arr[i] is present in the map if (map.count(arr[i]) == 0) { // Update left[i] to 0 // and update the value // of arr[i] in map left[i] = 0; map[arr[i]] = make_pair(1, i); } // Otherwise, get the value from // the map and update left[i] else { pair<int, int> tmp = map[arr[i]]; left[i] = (tmp.first) * (i - tmp.second) + left[tmp.second]; map[arr[i]] = make_pair(tmp.first + 1, i); } } // Clear the map to calculate right[] array map.clear(); // Traverse the array arr[] in reverse for (int i = n - 1; i >= 0; i--) { // If arr[i] is present in the map if (map.count(arr[i]) == 0) { // Update right[i] to 0 // and update the value // of arr[i] in the map right[i] = 0; map[arr[i]] = make_pair(1, i); } // Otherwise get the value from // the map and update right[i] else { pair<int, int> tmp = map[arr[i]]; right[i] = (tmp.first) * (abs(i - tmp.second)) + right[tmp.second]; map[arr[i]] = make_pair(tmp.first + 1, i); } } // Iterate in the range [0, N-1] // and print the sum of left[i] // and right[i] as the result for (int i = 0; i < n; i++) cout << left[i] + right[i] << " ";}int main(){ int arr[] = { 1, 3, 1, 1, 2 }; int N = sizeof(arr) / sizeof(arr[0]); findSum(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Stores the count of occurrences // and previous index of every element static class pair { int count, prevIndex; // Constructor pair(int count, int prevIndex) { this.count = count; this.prevIndex = prevIndex; } } // Function to calculate the sum of // absolute differences of indices // of occurrences of array element static void findSum(int[] arr, int n) { // Stores the count of elements // and their previous indices Map<Integer, pair> map = new HashMap<>(); // Initialize 2 arrays left[] // and right[] of size N int[] left = new int[n]; int[] right = new int[n]; // Traverse the given array for (int i = 0; i < n; i++) { // If arr[i] is present in the Map if (!map.containsKey(arr[i])) { // Update left[i] to 0 // and update the value // of arr[i] in map left[i] = 0; map.put(arr[i], new pair(1, i)); } // Otherwise, get the value from // the map and update left[i] else { pair tmp = map.get(arr[i]); left[i] = (tmp.count) * (i - tmp.prevIndex) + left[tmp.prevIndex]; map.put( arr[i], new pair( tmp.count + 1, i)); } } // Clear the map to calculate right[] array map.clear(); // Traverse the array arr[] in reverse for (int i = n - 1; i >= 0; i--) { // If arr[i] is present in theMap if (!map.containsKey(arr[i])) { // Update right[i] to 0 // and update the value // of arr[i] in the Map right[i] = 0; map.put(arr[i], new pair(1, i)); } // Otherwise get the value from // the map and update right[i] else { pair tmp = map.get(arr[i]); right[i] = (tmp.count) * (Math.abs(i - tmp.prevIndex)) + right[tmp.prevIndex]; map.put( arr[i], new pair( tmp.count + 1, i)); } } // Iterate in the range [0, N-1] // and print the sum of left[i] // and right[i] as the result for (int i = 0; i < n; i++) System.out.print( left[i] + right[i] + " "); } // Driver Code public static void main(String[] args) { int[] arr = { 1, 3, 1, 1, 2 }; int N = arr.length; findSum(arr, N); }} |
Python3
# Python program for the above approach# Stores the count of occurrences # and previous index of every elementclass pair: def __init__(self, count,prevIndex): self.count = count; self.prevIndex = prevIndex; # Function to calculate the sum of # absolute differences of indices # of occurrences of array elementdef findSum(arr,n): # Stores the count of elements # and their previous indices map = {}; # Initialize 2 arrays left[] # and right[] of size N left = [0 for i in range(n)]; right = [0 for i in range(n)]; # Traverse the given array for i in range(n): # If arr[i] is present in the Map if (arr[i] not in map): # Update left[i] to 0 # and update the value # of arr[i] in map left[i] = 0; map[arr[i]] = pair(1, i); # Otherwise, get the value from # the map and update left[i] else: tmp = map[arr[i]]; left[i] = (tmp.count) * (i - tmp.prevIndex) + left[tmp.prevIndex] map[arr[i]] = pair( tmp.count + 1, i); # Clear the map to calculate right[] array map.clear(); # Traverse the array arr[] in reverse for i in range (n - 1, -1, -1): # If arr[i] is present in theMap if (arr[i] not in map): # Update right[i] to 0 # and update the value # of arr[i] in the Map right[i] = 0; map[arr[i]] = pair(1, i); # Otherwise get the value from # the map and update right[i] else: tmp = map[arr[i]]; right[i] = (tmp.count) * (abs(i - tmp.prevIndex)) + right[tmp.prevIndex]; map[arr[i]] = pair(tmp.count + 1, i); # Iterate in the range [0, N-1] # and print the sum of left[i] # and right[i] as the result for i in range(n): print(left[i] + right[i], end=" ");# Driver Codearr=[1, 3, 1, 1, 2];N = len(arr);findSum(arr, N);# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Stores the count of occurrences // and previous index of every element class pair { public int count, prevIndex; // Constructor public pair(int count, int prevIndex) { this.count = count; this.prevIndex = prevIndex; } } // Function to calculate the sum of // absolute differences of indices // of occurrences of array element static void findSum(int[] arr, int n) { // Stores the count of elements // and their previous indices Dictionary<int, pair> map = new Dictionary<int, pair>(); // Initialize 2 arrays []left // and []right of size N int[] left = new int[n]; int[] right = new int[n]; // Traverse the given array for (int i = 0; i < n; i++) { // If arr[i] is present in the Map if (!map.ContainsKey(arr[i])) { // Update left[i] to 0 // and update the value // of arr[i] in map left[i] = 0; map.Add(arr[i], new pair(1, i)); } // Otherwise, get the value from // the map and update left[i] else { pair tmp = map[arr[i]]; left[i] = (tmp.count) * (i - tmp.prevIndex) + left[tmp.prevIndex]; map[arr[i]] = new pair( tmp.count + 1, i); } } // Clear the map to calculate []right array map.Clear(); // Traverse the array []arr in reverse for (int i = n - 1; i >= 0; i--) { // If arr[i] is present in theMap if (!map.ContainsKey(arr[i])) { // Update right[i] to 0 // and update the value // of arr[i] in the Map right[i] = 0; map.Add(arr[i], new pair(1, i)); } // Otherwise get the value from // the map and update right[i] else { pair tmp = map[arr[i]]; right[i] = (tmp.count) * (Math.Abs(i - tmp.prevIndex)) + right[tmp.prevIndex]; map[arr[i]] = new pair( tmp.count + 1, i); } } // Iterate in the range [0, N-1] // and print the sum of left[i] // and right[i] as the result for (int i = 0; i < n; i++) Console.Write( left[i] + right[i] + " "); } // Driver Code public static void Main(String[] args) { int[] arr = { 1, 3, 1, 1, 2 }; int N = arr.Length; findSum(arr, N); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approach// Stores the count of occurrences // and previous index of every elementclass pair{ constructor(count,prevIndex) { this.count = count; this.prevIndex = prevIndex; }}// Function to calculate the sum of // absolute differences of indices // of occurrences of array elementfunction findSum(arr,n){ // Stores the count of elements // and their previous indices let map = new Map(); // Initialize 2 arrays left[] // and right[] of size N let left = new Array(n); let right = new Array(n); // Traverse the given array for (let i = 0; i < n; i++) { // If arr[i] is present in the Map if (!map.has(arr[i])) { // Update left[i] to 0 // and update the value // of arr[i] in map left[i] = 0; map.set(arr[i], new pair(1, i)); } // Otherwise, get the value from // the map and update left[i] else { let tmp = map.get(arr[i]); left[i] = (tmp.count) * (i - tmp.prevIndex) + left[tmp.prevIndex]; map.set( arr[i], new pair( tmp.count + 1, i)); } } // Clear the map to calculate right[] array map.clear(); // Traverse the array arr[] in reverse for (let i = n - 1; i >= 0; i--) { // If arr[i] is present in theMap if (!map.has(arr[i])) { // Update right[i] to 0 // and update the value // of arr[i] in the Map right[i] = 0; map.set(arr[i], new pair(1, i)); } // Otherwise get the value from // the map and update right[i] else { let tmp = map.get(arr[i]); right[i] = (tmp.count) * (Math.abs(i - tmp.prevIndex)) + right[tmp.prevIndex]; map.set( arr[i], new pair( tmp.count + 1, i)); } } // Iterate in the range [0, N-1] // and print the sum of left[i] // and right[i] as the result for (let i = 0; i < n; i++) document.write( left[i] + right[i] + " ");}// Driver Codelet arr=[1, 3, 1, 1, 2];let N = arr.length;findSum(arr, N);// This code is contributed by unknown2108</script> |
Output:
5 0 3 4 0
Time Complexity: O(N*log(N))
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!
