Dada una array ordenada arr[] de N enteros positivos distintos. La tarea es generar una array tal que el elemento en cada índice de la nueva array sea la suma de las diferencias absolutas del elemento correspondiente con todos los demás elementos de la array dada.
Entrada: arr[] = [2, 3, 5]
Salida: [4, 3, 5]
Explicación:
distancia(2) = |2 – 3| + |2 – 5| = 4
distancia(3) = |3 – 2| + |3 – 5| = 3
distancia(5) = |5 – 2| + |5 – 3| = 5
Por lo tanto, devolveremos [4, 3, 5]Entrada: arr[] = [2, 3, 5, 6]
Salida: [8, 6, 6, 8]
Explicación:
distancia(2) = |2 – 3| + |2 – 5| + |2 – 6|= 8
distancia(3) = |3 – 2| + |3 – 5| + |3 – 6|= 6
distancia(5) = |5 – 2| + |5 – 3| + |5 – 6|= 6
distancia(6) = |6 – 2| + |6 – 3| + |6 – 5|= 8
Por lo tanto, devolveremos [8, 6, 6, 8]
Enfoque ingenuo: la idea es generar todos los pares posibles para cada elemento en la array arr[] y agregar la suma de la diferencia absoluta de los pares para cada elemento en la nueva array. Imprima la array después de los pasos anteriores para todos los elementos.
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 return the new array
vector<int> calculate(int* arr, int n)
{
// Initialize the Arraylist
vector<int> ans;
// Sum of absolute differences
// of element with all elements
for(int i = 0; i < n; i++)
{
// Initialize int sum to 0
int sum = 0;
for(int j = 0; j < n; j++)
{
sum += abs(arr[i] - arr[j]);
}
// Add the value of sum to ans
ans.push_back(sum);
}
// Return the final ans
return ans;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 2, 3, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
vector<int> ans = calculate(arr, n);
cout << "[";
for(auto itr : ans)
cout << itr << ", ";
cout << "]";
return 0;
}
// This code is contributed by jrishabh99
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to return the new array
private static List<Integer>
calculate(int[] arr)
{
// Length of the arraylist
int n = arr.length;
// Initialize the Arraylist
List<Integer> ans
= new ArrayList<Integer>();
// Sum of absolute differences
// of element with all elements
for (int i = 0;
i < arr.length; i++) {
// Initialize int sum to 0
int sum = 0;
for (int j = 0;
j < arr.length; j++) {
sum += Math.abs(arr[i] - arr[j]);
}
// Add the value of sum to ans
ans.add(sum);
}
// Return the final ans
return ans;
}
// Driver Code
public static void
main(String[] args)
{
// Given array arr[]
int[] arr = { 2, 3, 5, 6 };
// Function Call
System.out.println(calculate(arr));
}
}
Python3
# Python3 program for the above approach # Function to return the new array # private static List<Integer> def calculate(arr): # Length of the arraylist n = len(arr) # Initialize the Arraylist ans = [] # Sum of absolute differences # of element with all elements for i in range(n): # Initialize sum to 0 sum = 0 for j in range(len(arr)): sum += abs(arr[i] - arr[j]) # Add the value of sum to ans ans.append(sum) # Return the final ans return ans # Driver Code if __name__ == '__main__': # Given array arr[] arr = [ 2, 3, 5, 6 ] # Function call print(calculate(arr)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to return the new array
private static List<int> calculate(int[] arr)
{
// Length of the arraylist
int n = arr.Length;
// Initialize the Arraylist
List<int> ans = new List<int>();
// Sum of absolute differences
// of element with all elements
for(int i = 0; i < arr.Length; i++)
{
// Initialize int sum to 0
int sum = 0;
for(int j = 0; j < arr.Length; j++)
{
sum += Math.Abs(arr[i] - arr[j]);
}
// Add the value of sum to ans
ans.Add(sum);
}
// Return the final ans
return ans;
}
// Driver Code
public static void Main(string[] args)
{
// Given array arr[]
int[] arr = { 2, 3, 5, 6 };
List<int> tmp = calculate(arr);
Console.Write("[");
for(int i = 0; i < tmp.Count; i++)
{
if(i != tmp.Count - 1)
{
Console.Write(tmp[i] + ", ");
}
else
{
Console.Write(tmp[i]);
}
}
Console.Write("]");
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program for
// the above approach
// Function to return the new array
function
calculate(arr)
{
// Length of the arraylist
let n = arr.length;
// Initialize the Arraylist
let ans
= [];
// Sum of absolute differences
// of element with all elements
for (let i = 0;
i < arr.length; i++) {
// Initialize let sum to 0
let sum = 0;
for (let j = 0;
j < arr.length; j++) {
sum += Math.abs(arr[i] - arr[j]);
}
// Add the value of sum to ans
ans.push(sum);
}
// Return the final ans
return ans;
}
// Driver Code
// Given array arr[]
let arr = [ 2, 3, 5, 6 ];
// Function Call
document.write(calculate(arr));
</script>
Producción:
[8, 6, 6, 8]
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es realizar un seguimiento de la resta acumulada de los valores a la izquierda y de la suma de valores a la derecha. La suma de la diferencia de todos los pares para cada elemento viene dada por:
num_of_elements_to_the_left * current_value -num_of_elements_to_the_right * current_value
- Encuentre la suma de todos los elementos en la array dada (digamos suma ).
- Inicializar sub como 0.
- Recorra la array dada y para cada elemento haga lo siguiente:
- Reste el valor actual arr[i] de la suma.
- Agregue la diferencia de todos los pares para cada elemento usando la fórmula a la array resultante:
sub + (i * arr[i]) - ((n - i - 1) * arr[i]) + sum
- Reste el valor actual arr[i] de la suma.
- Imprima la array resultante después de los pasos anteriores.
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 return list of
// total Distance of each element
// from other elements in array
vector<int> calculate(int arr[],
int n)
{
int sub = 0;
int sum = 0;
// Initialize the arraylist
vector<int> ans;
// Keep track of the
// accumulated of the
// sum of values to right
for (int i = n - 1;
i >= 0; i--)
sum += arr[i];
// Keep track of the
// accumulated subtraction
// of the values to the left
for (int i = 0; i < n; i++)
{
sum -= arr[i];
// Add the value to the
// resultant array ans[]
ans.push_back(sub + (i * arr[i]) -
((n - i - 1) *
arr[i]) + sum);
sub -= arr[i];
}
// Return the final
// answer
return ans;
}
// Driver Code
int main()
{
// Initialize the array
int arr[] = {2, 3, 5, 6};
int n = sizeof(arr) /
sizeof(arr[0]);
vector<int> ans = (calculate(arr, n));
for (int i = 0; i < n; i++)
cout << ans[i] << " ";
}
// This code is contributed by Chitranayal
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to return list of
// total Distance of each element
// from other elements in array
private static List<Integer>
calculate(int[] arr)
{
// Length of the array
int n = arr.length;
int sub = 0;
int sum = 0;
// Initialize the arraylist
List<Integer> ans
= new ArrayList<Integer>();
// Keep track of the accumulated
// of the sum of values to right
for (int i = n - 1; i >= 0; i--)
sum += arr[i];
// Keep track of the accumulated
// subtraction of the values to the left
for (int i = 0; i < arr.length; i++) {
sum -= arr[i];
// Add the value to the resultant
// array ans[]
ans.add(sub
+ (i * arr[i])
- ((n - i - 1)
* arr[i])
+ sum);
sub -= arr[i];
}
// return the final answer
return ans;
}
// Driver Code
public static void
main(String[] args)
{
// Initialize the array
int[] arr = { 2, 3, 5, 6 };
// Function Call
System.out.println(calculate(arr));
}
}
Python3
# Python3 program for the above approach # Function to return list of # total Distance of each element # from other elements in array def calculate (arr): # Length of the array n = len(arr) sub = 0 Sum = 0 # Initialize the ArrayList ans = [] # Keep track of the accumulated # of the sum of values to right for i in range(n - 1, -1, -1): Sum += arr[i] # Keep track of the accumulated # subtraction of values to left for i in range(len(arr)): Sum -= arr[i] # Add the value to the resultant # array ans[] ans.append(sub + (i * arr[i]) - ((n - i - 1) * arr[i]) + Sum) sub -= arr[i] # Return the final answer return ans # Driver Code if __name__ == '__main__': # Initialize the array arr = [ 2, 3, 5, 6 ] # Function call print(calculate(arr)) # This code is contributed by himanshu77
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return list of
// total Distance of each element
// from other elements in array
private static List<int> calculate(int[] arr)
{
// Length of the array
int n = arr.Length;
int sub = 0;
int sum = 0;
// Initialize the arraylist
List<int> ans = new List<int>();
// Keep track of the accumulated
// of the sum of values to right
for(int i = n - 1; i >= 0; i--)
sum += arr[i];
// Keep track of the accumulated
// subtraction of the values to the left
for(int i = 0; i < arr.Length; i++)
{
sum -= arr[i];
// Add the value to the resultant
// array ans[]
ans.Add(sub + (i * arr[i]) -
((n - i - 1) *
arr[i]) + sum);
sub -= arr[i];
}
// return the readonly answer
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Initialize the array
int[] arr = { 2, 3, 5, 6 };
// Function Call
Console.Write("[ ");
foreach(int i in calculate(arr))
Console.Write(i + ", ");
Console.Write("]");
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript program for the
// above approach
// Function to return list of
// total Distance of each element
// from other elements in array
function calculate(arr, n)
{
var sub = 0;
var sum = 0;
// Initialize the arraylist
var ans = [];
// Keep track of the
// accumulated of the
// sum of values to right
for (var i = n - 1;
i >= 0; i--)
sum += arr[i];
// Keep track of the
// accumulated subtraction
// of the values to the left
for (var i = 0; i < n; i++)
{
sum -= arr[i];
// Add the value to the
// resultant array ans[]
ans.push(sub + (i * arr[i]) -
((n - i - 1) *
arr[i]) + sum);
sub -= arr[i];
}
// Return the final
// answer
return ans;
}
// Driver Code
// Initialize the array
var arr = [2, 3, 5, 6]
var n = arr.length;
var ans = (calculate(arr, n));
for (var i = 0; i < n; i++)
document.write( ans[i] + " ");
// This code is contributed by famously.
</script>
Producción:
[8, 6, 6, 8]
Complejidad temporal: O(N)
Complejidad espacial: O(N)