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