Dada una array ordenada de elementos distintos, la tarea es encontrar la suma de las diferencias absolutas de todos los pares en la array dada.
Ejemplos:
Input : arr[] = {1, 2, 3, 4}
Output: 10
Sum of |2-1| + |3-1| + |4-1| +
|3-2| + |4-2| + |4-3| = 10
Input : arr[] = {1, 8, 9, 15, 16}
Output: 74
Input : arr[] = {1, 2, 3, 4, 5, 7, 9, 11, 14}
Output: 188
Una solución simple para este problema es buscar uno por uno cada par, tomar su diferencia y sumarlos. La complejidad temporal para este enfoque es O(n 2 ).
Una solución eficiente para este problema necesita una simple observación. Dado que la array está ordenada y los elementos son distintos cuando tomamos la suma de la diferencia absoluta de pares, cada elemento en la i-ésima posición se suma ‘i’ veces y se resta ‘n-1-i’ veces.
Por ejemplo, en {1,2,3,4} el elemento en el índice 2 es arr[2] = 3, por lo que todos los pares que tienen 3 como un elemento serán (1,3), (2,3) y (3,4) , ahora, cuando tomamos la suma de la diferencia absoluta de pares, entonces para todos los pares en los que 3 está presente como un elemento, la suma será = (3-1) + (3-2) + (4-3). Podemos ver que 3 se suma i = 2 veces y se resta n-1-i = (4-1-2) = 1 vez.
La expresión generalizada para cada elemento será sum = sum + (i*a[i]) – (n-1-i)*a[i].
C++
// C++ program to find sum of absolute differences
// in all pairs in a sorted array of distinct numbers
#include<bits/stdc++.h>
using namespace std;
// Function to calculate sum of absolute difference
// of all pairs in array
// arr[] --> array of elements
int sumPairs(int arr[],int n)
{
// final result
int sum = 0;
for (int i=n-1; i>=0; i--)
sum += i*arr[i] - (n-1-i)*arr[i];
return sum;
}
// Driver program to run the case
int main()
{
int arr[] = {1, 8, 9, 15, 16};
int n = sizeof(arr)/sizeof(arr[0]);
cout << sumPairs(arr, n);
return 0;
}
// This code is contributed by Sania Kumari Gupta
C
// C program to find sum of absolute differences
// in all pairs in a sorted array of distinct numbers
#include <stdio.h>
// Function to calculate sum of absolute difference
// of all pairs in array
// arr[] --> array of elements
int sumPairs(int arr[], int n)
{
// final result
int sum = 0;
for (int i = n - 1; i >= 0; i--)
sum += i * arr[i] - (n - 1 - i) * arr[i];
return sum;
}
// Driver program to run the case
int main()
{
int arr[] = { 1, 8, 9, 15, 16 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", sumPairs(arr, n));
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java program to find sum of absolute differences in all
// pairs in a sorted array of distinct numbers
class GFG {
// Function to calculate sum of absolute
// difference of all pairs in array
// arr[] --> array of elements
static int sumPairs(int arr[], int n)
{
// final result
int sum = 0;
for (int i = n - 1; i >= 0; i--)
sum += i * arr[i] - (n - 1 - i) * arr[i];
return sum;
}
// Driver program
public static void main(String arg[])
{
int arr[] = { 1, 8, 9, 15, 16 };
int n = arr.length;
System.out.print(sumPairs(arr, n));
}
}
// This code is contributed by Sania Kumari Gupta
Python3
# Python3 program to find sum of # absolute differences in all pairs # in a sorted array of distinct numbers # Function to calculate sum of absolute # difference of all pairs in array # arr[] --> array of elements def sumPairs(arr, n): # final result sum = 0 for i in range(n - 1, -1, -1): sum += i*arr[i] - (n-1-i) * arr[i] return sum # Driver program arr = [1, 8, 9, 15, 16] n = len(arr) print(sumPairs(arr, n)) # This code is contributed by Anant Agarwal.
C#
// C# program to find sum of absolute
// differences in all pairs in a sorted
// array of distinct numbers
using System;
class GFG {
// Function to calculate sum of absolute
// difference of all pairs in array
// arr[] --> array of elements
static int sumPairs(int []arr, int n)
{
// final result
int sum = 0;
for (int i = n - 1; i >= 0; i--)
sum += i * arr[i] - (n - 1 - i)
* arr[i];
return sum;
}
// Driver program
public static void Main()
{
int []arr = { 1, 8, 9, 15, 16 };
int n = arr.Length;
Console.Write(sumPairs(arr, n));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find sum of absolute differences
// in all pairs in a sorted array of distinct numbers
// Function to calculate sum of absolute difference
// of all pairs in array
// arr[] --> array of elements
function sumPairs($arr,$n)
{
// final result
$sum = 0;
for ($i=$n-1; $i>=0; $i--)
$sum = $sum + $i*$arr[$i] - ($n-1-$i)*$arr[$i];
return $sum;
}
// Driver program to run the case
$arr = array(1, 8, 9, 15, 16);
$n = sizeof($arr)/sizeof($arr[0]);
echo sumPairs($arr, $n);
?>
Javascript
<script>
// JavaScript program to find
// sum of absolute differences
// in all pairs in a sorted array
// of distinct numbers
// Function to calculate sum of absolute difference
// of all pairs in array
// arr[] --> array of elements
function sumPairs( arr, n)
{
// final result
let sum = 0;
for (let i=n-1; i>=0; i--)
sum += i*arr[i] - (n-1-i)*arr[i];
return sum;
}
// Driver program to run the case
let arr = [ 1, 8, 9, 15, 16 ];
let n = arr.length;
document.write(sumPairs(arr, n));
</script>
74
Tiempo Complejidad: O(n)
Espacio auxiliar: O(1)
¿Qué pasa si la array no está ordenada?
La solución eficiente también es mejor para los casos en los que la array no está ordenada. Podemos ordenar la array primero en tiempo O(n Log n) y luego encontrar el valor requerido en O(n). Entonces, la complejidad del tiempo general es O (n Log n), que aún es mejor que O (n 2 )
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA