Suma de la diferencia mínima absoluta de cada elemento de la array

Posted on by Rudeus Greyrat

Dada una array de n enteros distintos. El problema es encontrar la suma de la mínima diferencia absoluta de cada elemento de la array. Para un elemento x presente en el índice i de la array, su diferencia absoluta mínima se calcula como: Diferencia absoluta mínima 
(x) = min(abs(x – arr[j])), donde 1 <= j <= n y j ! = i y abs es el valor absoluto. 
Restricción de entrada: 2 <= n

Ejemplos: 

Input : arr = {4, 1, 5}
Output : 5
Sum of absolute differences is |4-5| + |1-4| + |5-4|

Input : arr = {5, 10, 1, 4, 8, 7}
Output : 9

Input : {12, 10, 15, 22, 21, 20, 1, 8, 9}
Output : 18

Enfoque ingenuo: usar dos bucles. Elija un elemento de la array usando el bucle externo y calcule su diferencia absoluta con el resto de los elementos de la array usando el bucle interno. Encuentra el valor absoluto mínimo y súmalo a la suma. Tiempo Complejidad O(n 2 ). 

Enfoque eficiente: 

Los siguientes pasos son:

  1. Ordene la array de tamaño n .
  2. Para el primer elemento de la array, su diferencia mínima absoluta se calcula utilizando el segundo elemento de la array.
  3. Para el último elemento de la array, su diferencia mínima absoluta se calcula utilizando el penúltimo elemento de la array.
  4. Para el resto de los elementos de la array, 1 <= i <= n-2 , la diferencia absoluta mínima para un elemento en el índice i se calcula como: minAbsDiff = min( abs(arr[i] – arr[i-1]), abs(ar[i] – arr[i+1]) ).

Implementación:

C++

// C++ implementation to find the sum of minimum
// absolute difference of each array element
#include <bits/stdc++.h>
using namespace std;
 
// function to find the sum of
// minimum absolute difference
int sumOfMinAbsDifferences(int arr[], int n)
{
    // sort the given array
    sort(arr, arr+n);
     
    // initialize sum
    int sum = 0;
     
    // min absolute difference for
    // the 1st array element
    sum += abs(arr[0] - arr[1]);
     
    // min absolute difference for
    // the last array element
    sum += abs(arr[n-1] - arr[n-2]);
     
    // find min absolute difference for rest of the
    // array elements and add them to sum
    for (int i=1; i<n-1; i++)
        sum += min(abs(arr[i] - arr[i-1]), abs(arr[i] - arr[i+1]));
         
    // required sum   
    return sum;   
}
 
// Driver program to test above
int main()
{
    int arr[] = {5, 10, 1, 4, 8, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Sum = "
         << sumOfMinAbsDifferences(arr, n);
}

Java

// java implementation to find the sum
// of minimum absolute difference of
// each array element
import java.*;
import java.util.Arrays;
 
public class GFG {
     
    // function to find the sum of
    // minimum absolute difference
    static int sumOfMinAbsDifferences(
                         int arr[] ,int n)
    {
         
        // sort the given array
        Arrays.sort(arr);
         
        // initialize sum
        int sum = 0;
         
        // min absolute difference for
        // the 1st array element
        sum += Math.abs(arr[0] - arr[1]);
         
        // min absolute difference for
        // the last array element
        sum += Math.abs(arr[n-1] - arr[n-2]);
         
        // find min absolute difference for
        // rest of the array elements and
        // add them to sum
        for (int i = 1; i < n - 1; i++)
            sum +=
            Math.min(Math.abs(arr[i] - arr[i-1]),
                    Math.abs(arr[i] - arr[i+1]));
             
        // required sum
        return sum;
    }    
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = {5, 10, 1, 4, 8, 7};
        int n = arr.length;
         
        System.out.println( "Sum = "
        + sumOfMinAbsDifferences(arr, n));
    }
}
 
// This code is contributed by Sam007.

Python3

# Python implementation to find the
# sum of minimum absolute difference
# of each array element
 
# function to find the sum of
# minimum absolute difference
 
def sumOfMinAbsDifferences(arr,n):
    # sort the given array
    arr.sort()
    # initialize sum
    sum = 0
         
    # min absolute difference for
    # the 1st array element
    sum += abs(arr[0] - arr[1]);
         
    # min absolute difference for
    # the last array element
    sum += abs(arr[n - 1] - arr[n - 2]);
         
    # find min absolute difference for
    # rest of the array elements and
    # add them to sum
    for i in range(1, n - 1):
        sum += min(abs(arr[i] - arr[i - 1]),
                  abs(arr[i] - arr[i + 1]))
             
    # required sum
    return sum;
         
 
# Driver code
arr = [5, 10, 1, 4, 8, 7]
n = len(arr)
print( "Sum = ", sumOfMinAbsDifferences(arr, n))
     
     
#This code is contributed by Sam007

C#

// C# implementation to find the sum
// of minimum absolute difference of
// each array element
using System;
         
public class GFG {
     
    // function to find the sum of
    // minimum absolute difference
    static int sumOfMinAbsDifferences(
                         int []arr ,int n)
    {
         
        // sort the given array
        Array.Sort(arr);
         
        // initialize sum
        int sum = 0;
         
        // min absolute difference for
        // the 1st array element
        sum += Math.Abs(arr[0] - arr[1]);
         
        // min absolute difference for
        // the last array element
        sum += Math.Abs(arr[n-1] - arr[n-2]);
         
        // find min absolute difference for
        // rest of the array elements and
        // add them to sum
        for (int i = 1; i < n - 1; i++)
            sum +=
            Math.Min(Math.Abs(arr[i] - arr[i-1]),
                    Math.Abs(arr[i] - arr[i+1]));
             
        // required sum
        return sum;
    }    
 
    // Driver code
    public static void Main ()
    {
        int []arr = {5, 10, 1, 4, 8, 7};
        int n = arr.Length;
         
        Console.Write( "Sum = "
        + sumOfMinAbsDifferences(arr, n));
    }
}
 
// This code is contributed by Sam007.

PHP

<?php
// PHP implementation to find
// the sum of minimum absolute
// difference of each array element
 
// function to find the sum of
// minimum absolute difference
function sumOfMinAbsDifferences($arr, $n)
{
     
    // sort the given array
    sort($arr);
    sort( $arr,$n);
     
    // initialize sum
    $sum = 0;
     
    // min absolute difference for
    // the 1st array element
    $sum += abs($arr[0] - $arr[1]);
     
    // min absolute difference for
    // the last array element
    $sum += abs($arr[$n - 1] - $arr[$n - 2]);
     
    // find min absolute difference
    // for rest of the array elements
    // and add them to sum
    for ($i = 1; $i < $n - 1; $i++)
        $sum += min(abs($arr[$i] - $arr[$i - 1]),
                   abs($arr[$i] - $arr[$i + 1]));
         
    // required sum
    return $sum;
}
 
    // Driver Code
    $arr = array(5, 10, 1, 4, 8, 7);
    $n = sizeof($arr);
    echo "Sum = ", sumOfMinAbsDifferences($arr, $n);
 
// This code is contributed by nitin mittal.
?>

Javascript

<script>
 
    // Javascript implementation to find the sum
    // of minimum absolute difference of
    // each array element
     
    // function to find the sum of
    // minimum absolute difference
    function sumOfMinAbsDifferences(arr, n)
    {
           
        // sort the given array
        arr.sort(function(a, b){return a - b});
           
        // initialize sum
        let sum = 0;
           
        // min absolute difference for
        // the 1st array element
        sum += Math.abs(arr[0] - arr[1]);
           
        // min absolute difference for
        // the last array element
        sum += Math.abs(arr[n-1] - arr[n-2]);
           
        // find min absolute difference for
        // rest of the array elements and
        // add them to sum
        for (let i = 1; i < n - 1; i++)
            sum +=
            Math.min(Math.abs(arr[i] - arr[i-1]),
                    Math.abs(arr[i] - arr[i+1]));
               
        // required sum
        return sum;
    }
     
    let arr = [5, 10, 1, 4, 8, 7];
    let n = arr.length;
 
    document.write( "Sum = " + sumOfMinAbsDifferences(arr, n));
     
</script>
Producción

Sum = 9

Complejidad de Tiempo: O(n log n)
Espacio Auxiliar: O(1)

Este artículo es una contribución de Ayush Jauhari . 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *