Dada una array arr[] que consta de N enteros, la tarea de cada elemento de la array arr[i] es imprimir la suma de |i – j| para todos los posibles índices j tales que arr[i] = arr[j] .
Ejemplos:
Entrada: arr[] = {1, 3, 1, 1, 2}
Salida: 5 0 3 4 0
Explicación:
Para arr[0], sum = |0 – 0| + |0 – 2| + |0 – 3| = 5.
Para arr[1], suma = |1 – 1| = 0.
Para arr[2], suma = |2 – 0| + |2 – 2| + |2 – 3| = 3.
Para arr[3], suma = |3 – 0| + |3 – 2| + |3 – 3| = 4.
Para arr[4], suma = |4 – 4| = 0.
Por lo tanto, la salida requerida es 5 0 3 4 0.Entrada: arr[] = {1, 1, 1}
Salida: 3 2 3
Enfoque ingenuo: el enfoque más simple es recorrer la array dada y para cada elemento arr[i] ( 0 ≤ i ≤ N ), recorrer la array y verificar si arr[i] es igual que arr[j] ( 0 ≤ j ≤ N ). Si se determina que es cierto, agregue abs(i – j) a la suma imprima la suma obtenida para cada elemento de la array.
Complejidad de tiempo: O(N 2 ) donde N es el tamaño de la array dada.
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es utilizar la estructura de datos del mapa para optimizar el enfoque anterior. Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa para almacenar el vector de índices para repeticiones de cada elemento único presente en la array.
- Recorra la array dada de i = 0 a N – 1 y para cada elemento de la array arr[i] , inicialice la suma con 0 y recorra el vector map[arr[i]] que almacena los índices de las ocurrencias del elemento arr[ yo] .
- Para cada valor j presente en el vector, incremente la suma en abs(i – j) .
- Después de atravesar el vector, almacene la suma del elemento en el índice i e imprima la suma.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
5 0 3 4 0
Complejidad de tiempo: O(N * L) donde N es el tamaño de la array dada y L es la frecuencia máxima de cualquier elemento de la array.
Espacio Auxiliar: O(N)