Given an array arr[] of size N. The task is to find an array of size N such that the ith element is the summation of |i – j| for all j such that arr[i] is equal to arr[j].
Examples:
Input: arr = {2, 1, 4, 1, 2, 4, 4}
Output: {4, 2, 7, 2, 4, 4, 5}
Explanation:
=> Index 0: Another 2 is found at index 4. |0 – 4| = 4
=> Index 1: Another 1 is found at index 3. |1 – 3| = 2
=> Index 2: Two more 4s are found at indices 5 and 6. |2 – 5| + |2 – 6| = 7
=> Index 3: Another 1 is found at index 1. |3 – 1| = 2
=> Index 4: Another 2 is found at index 0. |4 – 0| = 4
=> Index 5: Two more 4s are found at indices 2 and 6. |5 – 2| + |5 – 6| = 4
=> Index 6: Two more 4s are found at indices 2 and 5. |6 – 2| + |6 – 5| = 5Input: arr = {1, 10, 510, 10}
Output: {0 2 0 2}
A Naive Approach:
Iterate over the array and for each element run another loop for finding the similar elements, if similar elements found then keep sum of difference between their indices.
Follow the steps below to implement the above idea:
- Initialise an array result for keeping answers
- Run a loop for i = 0 to n – 1 (including)
- Initialise a variable sum = 0;
- Run another loop for j = 0 to n – 1 (including)
- Check if arr[i] is equal to arr[j]
- Add the absolute difference between their indices into sum
- Insert the sum into result.
- Finally, return result.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the resultant arrayvector<long long> getDistances(vector<long long>& arr){ int n = arr.size(); vector<long long> result; // Run a loop for i = 0 to n - 1 (including) for (int i = 0; i < n; i++) { // Initialise a variable sum = 0; long long sum = 0; // Run another loop for j = 0 to n - 1 (including) for (int j = 0; j < n; j++) { // Check if arr[i] is equal to arr[j] if (arr[i] == arr[j]) { // Add the absolute difference of their // indices sum += abs(i - j); } } // Insert the sum into result. result.push_back(sum); } // Finally return result. return result;}// Driver codeint main(){ vector<long long> arr = { 2, 1, 4, 1, 2, 4, 4 }; // Function call vector<long long> result = getDistances(arr); for (auto i : result) { cout << i << " "; } return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to find the resultant array static int[] getDistances(int[] arr) { int n = arr.length; int[] result = new int[n]; // Run a loop for i = 0 to n - 1 (including) for (int i = 0; i < n; i++) { // Initialise a variable sum = 0; int sum = 0; // Run another loop for j = 0 to n - 1 // (including) for (int j = 0; j < n; j++) { // Check if arr[i] is equal to arr[j] if (arr[i] == arr[j]) { // Add the absolute difference of their // indices sum += Math.abs(i - j); } } // Insert the sum into result. result[i] = sum; } // Finally return result. return result; } public static void main(String[] args) { int[] arr = { 2, 1, 4, 1, 2, 4, 4 }; // Function call int[] result = getDistances(arr); for (int i = 0; i < result.length; i++) { System.out.print(result[i] + " "); } }}// This code is contributed by lokesh. |
Python3
# Python code to implement the approach# Function to find the resultant arraydef getDistances(arr): n=len(arr) result=[] # Run a loop for i = 0 to n - 1 (including) for i in range(n): # Initialise a variable sum = 0 sum=0 # Run another loop for j = 0 to n - 1 (including) for j in range(n): # Check if arr[i] is equal to arr[j] if(arr[i]==arr[j]): # Add the absolute difference of their # indices sum+=abs(i-j) # Insert the sum into result. result.append(sum) # Finally return result. return result # Driver codearr=[2, 1, 4, 1, 2, 4, 4]#Function callresult=getDistances(arr)for i in result: print(i,end=" ") # This code is contributed by Pushpesh Raj |
C#
// C# code to implement the approachusing System;public class GFG { // Function to find the resultant array static int[] getDistances(int[] arr) { int n = arr.Length; int[] result = new int[n]; // Run a loop for i = 0 to n - 1 (including) for (int i = 0; i < n; i++) { // Initialise a variable sum = 0; int sum = 0; // Run another loop for j = 0 to n - 1 // (including) for (int j = 0; j < n; j++) { // Check if arr[i] is equal to arr[j] if (arr[i] == arr[j]) { // Add the absolute difference of their // indices sum += Math.Abs(i - j); } } // Insert the sum into result. result[i] = sum; } // Finally return result. return result; } static public void Main() { // Code int[] arr = { 2, 1, 4, 1, 2, 4, 4 }; // Function call int[] result = getDistances(arr); for (int i = 0; i < result.Length; i++) { Console.Write(result[i] + " "); } }}// This code is contributed by lokeshmvs21. |
Javascript
// JS code to implement the approach// Function to find the resultant arrayfunction getDistances(arr){ let n = arr.length; let result = []; // Run a loop for i = 0 to n - 1 (including) for (let i = 0; i < n; i++) { // Initialise a variable sum = 0; let sum = 0; // Run another loop for j = 0 to n - 1 (including) for (let j = 0; j < n; j++) { // Check if arr[i] is equal to arr[j] if (arr[i] == arr[j]) { // Add the absolute difference of their // indices sum += Math.abs(i - j); } } // Insert the sum into result. result.push(sum); } // Finally return result. return result;}// Driver codelet arr = [ 2, 1, 4, 1, 2, 4, 4 ];// Function calllet result = getDistances(arr);let ans = "";for(let i = 0; i < result.length; i++) ans += result[i]+" ";console.log(ans);// This code is contributed by akashish__ |
Output
4 2 7 2 4 4 5
Time Complexity: O(N2)
Auxiliary Space: O(N)
An approach using Hashing:
Keep track of frequency and sum of the index of similar elements. Iterate over the array and calculate the sum of indices to the left of the current index which is similar to the current element.
Similarly, calculate the sum of indices to the right of the current index which is similar to the current element. The result for the ith index would be the sum of all the differences.
Illustration:
Consider the arr = {1, 2, 1, 1, 2, 1}
Now, If have to calculate the result for the index i = 3 which is element 1.
- To calculate the absolute value of the required result from the left would be something like => (i – 0) + (i – 2), which is equals to (2 * i – (0 + 2)).
- To generalise these, we can generate a formula to do the same: (frequency of similar element to the left* i) – (Sum of occurrences of such indices).
- To calculate the absolute value of required result from the right would be something like => (5 – i)
To generalise these, we can generate a formula to do the same: (Sum of occurrences of such indices) – (frequency of similar element to the right* i)- We can conclude from the above that: The result for the ith index would be:
result[i] = ((leftFreq * i) – leftSum) + (rightSum – (rightFreq * i)).
Follow the steps below to implement the above idea:
- Declare an unordered map unmap where the key is the element and the respective value is a pair consisting of total frequency and total sum.
- Declare an unordered map unmap2 where the key is the element and the respective value is a pair consisting of frequency till any index i and sum till ith index.
- Iterate over the array and update the unmap.
- Declare an array result[] for storing the result
- Iterate over the given array
- Update the result[i] with the value mentioned above.
- Update the unmap2 by increasing the current element’s frequency and the sum of all occurrences of similar elements till the ith index.
- Finally, return the result[] as the required answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the resultant arrayvector<long long> getDistances(vector<long long>& arr){ int n = arr.size(); // Declare a unordered map unmap for // storing the <key, <Total frequency, // total sum>> Declare a unordered map // unmap2 for storing the <key, // <frequency till any index i, sum // till ith index>> unordered_map<int, pair<long long, long long> > unmap, unmap2; // < key, <freq, sum>> // Iterate over the array and // update the unmap for (int i = 0; i < n; i++) { unmap[arr[i]] = { unmap[arr[i]].first + 1, unmap[arr[i]].second + i }; } // Declare an array result for // storing the result vector<long long> result(n); // Iterate over the given array for (int i = 0; i < n; i++) { auto curr = unmap2[arr[i]]; long long leftSum = curr.second; long long leftFreq = curr.first; long long rightSum = unmap[arr[i]].second - leftSum - i; long long rightFreq = unmap[arr[i]].first - leftFreq - 1; // Update the result[i] with value mentioned result[i] = ((leftFreq * i) - leftSum) + (rightSum - (rightFreq * i)); // Update the unmap2 by increasing // the current elements frequency // and sum of all occurrence of // similar element till ith index. unmap2[arr[i]] = { unmap2[arr[i]].first + 1, unmap2[arr[i]].second + i }; } // Finally return result. return result;}// Driver codeint main(){ vector<long long> arr = {2, 1, 4, 1, 2, 4, 4 }; // Function call vector<long long> result = getDistances(arr); for (auto i : result) { cout << i << " "; } return 0;} |
Java
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;public class GFG { public static void main(String[] args) { long[] arr = { 2, 1, 4, 1, 2, 4, 4 }; List<Long> result = getDistances(arr); for (Long i : result) { System.out.print(i + " "); } } public static List<Long> getDistances(long[] arr) { int n = arr.length; Map<Long, Pair> unmap = new HashMap<>(); Map<Long, Pair> unmap2 = new HashMap<>(); for (int i = 0; i < n; i++) { Pair pair = unmap.get(arr[i]); if (pair == null) { unmap.put(arr[i], new Pair(1, i)); } else { pair.freq++; pair.sum += i; unmap.put(arr[i], pair); } } List<Long> result = new ArrayList<>(n); for (int i = 0; i < n; i++) { Pair curr = unmap2.get(arr[i]); long leftSum = curr == null ? 0 : curr.sum; long leftFreq = curr == null ? 0 : curr.freq; Pair pair = unmap.get(arr[i]); long rightSum = pair.sum - leftSum - i; long rightFreq = pair.freq - leftFreq - 1; result.add((leftFreq * i) - leftSum + (rightSum - (rightFreq * i))); if (curr == null) { unmap2.put(arr[i], new Pair(1, i)); } else { curr.freq++; curr.sum += i; unmap2.put(arr[i], curr); } } return result; }}class Pair { long freq; long sum; public Pair(long freq, long sum) { this.freq = freq; this.sum = sum; }}// This code is contributed by akashish__ |
Python3
# Function to find the resultant arraydef getDistances(arr): n = len(arr) # Declare a unordered map unmap for # storing the <key, <Total frequency, # total sum>> Declare a unordered map # unmap2 for storing the <key, # <frequency till any index i, sum # till ith index>> unmap = {} unmap2 = {} # Iterate over the array and # update the unmap for i in range(n): if arr[i] in unmap: unmap[arr[i]] = (unmap[arr[i]][0] + 1, unmap[arr[i]][1] + i) else: unmap[arr[i]] = (1, i) # Declare an array result for # storing the result result = [0] * n # Iterate over the given array for i in range(n): if arr[i] in unmap2: curr = unmap2[arr[i]] else: curr = (0, 0) leftSum = curr[1] leftFreq = curr[0] if arr[i] in unmap: rightSum = unmap[arr[i]][1] - leftSum - i rightFreq = unmap[arr[i]][0] - leftFreq - 1 else: rightSum = 0 rightFreq = 0 # Update the result[i] with value mentioned result[i] = (leftFreq * i) - leftSum + rightSum - (rightFreq * i) # Update the unmap2 by increasing # the current elements frequency # and sum of all occurrence of # similar element till ith index. if arr[i] in unmap2: unmap2[arr[i]] = (unmap2[arr[i]][0] + 1, unmap2[arr[i]][1] + i) else: unmap2[arr[i]] = (1, i) # Finally return result. return result# Driver codearr = [2, 1, 4, 1, 2, 4, 4]# Function callresult = getDistances(arr)for i in result: print(i, end=" ")#This code is contributed by akashish__ |
C#
using System;using System.Collections.Generic;using System.Linq;public class GFG{ // Function to find the resultant array public static long[] GetDistances(long[] arr) { int n = arr.Length; // Declare a dictionary unmap for // storing the <key, <Total frequency, // total sum>> Declare a dictionary // unmap2 for storing the <key, // <frequency till any index i, sum // till ith index>> Dictionary<long, Tuple<long, long>> unmap = new Dictionary<long, Tuple<long, long>>(), unmap2 = new Dictionary<long, Tuple<long, long>>(); // < key, <freq, sum>> // Iterate over the array and // update the unmap for (int i = 0; i < n; i++) { if (unmap.ContainsKey(arr[i])) { unmap[arr[i]] = new Tuple<long, long>(unmap[arr[i]].Item1 + 1, unmap[arr[i]].Item2 + i); } else { unmap.Add(arr[i], new Tuple<long, long>(1, i)); } } // Declare an array result for // storing the result long[] result = new long[n]; // Iterate over the given array for (int i = 0; i < n; i++) { Tuple<long, long> curr = unmap2.ContainsKey(arr[i]) ? unmap2[arr[i]] : new Tuple<long, long>(0, 0); long leftSum = curr.Item2; long leftFreq = curr.Item1; long rightSum = unmap[arr[i]].Item2 - leftSum - i; long rightFreq = unmap[arr[i]].Item1 - leftFreq - 1; // Update the result[i] with value mentioned result[i] = (leftFreq * i) - leftSum + rightSum - (rightFreq * i); // Update the unmap2 by increasing // the current elements frequency // and sum of all occurrence of // similar element till ith index. if (unmap2.ContainsKey(arr[i])) { unmap2[arr[i]] = new Tuple<long, long>(unmap2[arr[i]].Item1 + 1, unmap2[arr[i]].Item2 + i); } else { unmap2.Add(arr[i], new Tuple<long, long>(1, i)); } } // Finally return result. return result; } // Driver code static public void Main (){ long[] arr = { 2, 1, 4, 1, 2, 4, 4 }; // Function call long[] result = GetDistances(arr); foreach (long i in result) { Console.Write(i+" "); } }}// This code is contributed by akashish__ |
Javascript
// JS code to implement the approach// Function to find the resultant arrayfunction getDistances( arr){ let n = arr.length; // Declare a unordered map unmap for // storing the <key, <Total frequency, // total sum>> Declare a unordered map // unmap2 for storing the <key, // <frequency till any index i, sum // till ith index>> let unmap = {}; let unmap2 = {}; // < key, <freq, sum>> for(let i=0;i<n;i++) { unmap[arr[i]] = {"first" : 0, "second" : 0}; unmap2[arr[i]] = {"first" : 0, "second" : 0}; } // Iterate over the array and // update the unmap for (let i = 0; i < n; i++) { unmap[arr[i]] = { "first" : unmap[arr[i]].first + 1, "second" : unmap[arr[i]].second + i }; } // Declare an array result for // storing the result let result = []; for(let i=0;i<n;i++) { result.push(0); } // Iterate over the given array for (let i = 0; i < n; i++) { let curr = unmap2[arr[i]]; let leftSum = curr.second; let leftFreq = curr.first; let rightSum = unmap[arr[i]].second - leftSum - i; let rightFreq = unmap[arr[i]].first - leftFreq - 1; // Update the result[i] with value mentioned result[i] = ((leftFreq * i) - leftSum) + (rightSum - (rightFreq * i)); // Update the unmap2 by increasing // the current elements frequency // and sum of all occurrence of // similar element till ith index. unmap2[arr[i]] = {"first": unmap2[arr[i]].first + 1, "second" : unmap2[arr[i]].second + i }; } // Finally return result. return result;}// Driver codelet arr = [2, 1, 4, 1, 2, 4, 4 ];// Function calllet result = getDistances(arr);console.log(result);// code by ksam24000 |
Output
4 2 7 2 4 4 5
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles:
- Introduction to Arrays – Data Structures and Algorithms Tutorials
- Introduction to Hashing – Data Structures and Algorithms Tutorials
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!
