Elemento de array con suma mínima de diferencias absolutas | conjunto 2

Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar un elemento X de la array tal que la suma de sus diferencias absolutas con cada elemento de la array sea mínima.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 3
Explicación:

1. Para el elemento arr[0](= 1): |(1 – 1)| + |(2 – 1)| + |(3 – 1)| + |(4 – 1)| + |(5 – 1)| = 0 + 1 + 2 + 3 + 4 = 10.
2. Para el elemento arr[1](= 2): |(1 – 2)| + |(2 – 2)| + |(3 – 2)| + |(4 – 2)| + |(5 – 2)| = 1 + 0 + 1 + 2 + 3 = 7.
3. Para el elemento arr[2](= 3): |(1 – 3)| + |(2 – 3)| + |(3 – 3)| + |(4 – 3)| + |(5 – 3)| = 2 + 1 + 0 + 1 + 2 = 6.
4. Para el elemento arr[3](= 4): |(1 – 4)| + |(2 – 4)| + |(3 – 4)| + |(4 – 4)| + |(5 – 4)| = 3 + 2 + 1 + 0 + 1 = 7.
5. Para el elemento arr[4](= 5): |(1 – 5)| + |(2 – 5)| + |(3 – 5)| + |(4 – 5)| + |(5 – 5)| = 4 + 3 + 2 + 1 + 0 = 10.

Por lo tanto, el elemento que tiene la suma mínima de diferencias absolutas con todos los elementos de la array es 3.

Entrada: arr[] = {15, 12, 13, 10}
Salida: 12

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es encontrar la suma de las diferencias absolutas de los elementos de la array con cada elemento de la array uno por uno, e imprimir ese elemento que tiene la menor suma de diferencias. 
Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque basado en la mediana: consulte la publicación anterior de este artículo para resolver este problema utilizando la técnica de búsqueda de la mediana. 
Complejidad temporal: O(NlogN) 
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar minimizando el valor de ( suma de todos los elementos de la array – X*N) para cada elemento de la array X y encontrar el elemento resultante X. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos res como arr[0] que almacena el elemento de array resultante cuya suma de diferencias absolutas de elementos de array con res es mínima.
• Encuentre la suma de los elementos de la array y guárdela en la variable, digamos sum .
• Inicialice una variable, diga minDiff como el valor de la suma .
• Recorra la array dada arr[] y si el valor absoluto de (sum – (arr[i] * N)) es menor que minDiff , actualice minDiff a este valor y res como el elemento de array actual, es decir, arr[i] .
• Después de completar los pasos anteriores, imprima el valor de res como el elemento de array resultante.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the element with
// minimum sum of differences between
// any elements in the array
int minimumDiff(int arr[], int N)
{
    // Stores the required X and
    // sum of absolute differences
    int res = arr[0], sum = 0;
 
    // Calculate sum of array elements
    for (int i = 0; i < N; i++)
        sum += arr[i];
 
    // The sum of absolute differences
    // can't be greater than sum
    int min_diff = sum;
 
    // Update res that gives
    // the minimum sum
    for (int i = 0; i < N; i++) {
 
        // If the current difference
        // is less than the previous
        // difference
        if (abs(sum - (arr[i] * N))
            < min_diff) {
 
            // Update min_diff and res
            min_diff = abs(sum - (arr[i] * N));
            res = arr[i];
        }
    }
 
    // Print the resultant value
    cout << res;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    minimumDiff(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
 
// Function to find the element with
// minimum sum of differences between
// any elements in the array
static void minimumDiff(int[] arr, int N)
{
     
    // Stores the required X and
    // sum of absolute differences
    int res = arr[0], sum = 0;
 
    // Calculate sum of array elements
    for(int i = 0; i < N; i++)
        sum += arr[i];
 
    // The sum of absolute differences
    // can't be greater than sum
    int min_diff = sum;
 
    // Update res that gives
    // the minimum sum
    for(int i = 0; i < N; i++)
    {
         
        // If the current difference
        // is less than the previous
        // difference
        if (Math.abs(sum - (arr[i] * N)) < min_diff)
        {
             
            // Update min_diff and res
            min_diff = Math.abs(sum - (arr[i] * N));
            res = arr[i];
        }
    }
 
    // Print the resultant value
    System.out.println(res);
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = arr.length;
     
    minimumDiff(arr, N);
}
}
 
// This code is contributed by subham348

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the element with
// minimum sum of differences between
// any elements in the array
static void minimumDiff(int[] arr, int N)
{
     
    // Stores the required X and
    // sum of absolute differences
    int res = arr[0], sum = 0;
 
    // Calculate sum of array elements
    for(int i = 0; i < N; i++)
        sum += arr[i];
 
    // The sum of absolute differences
    // can't be greater than sum
    int min_diff = sum;
 
    // Update res that gives
    // the minimum sum
    for(int i = 0; i < N; i++)
    {
         
        // If the current difference
        // is less than the previous
        // difference
        if (Math.Abs(sum - (arr[i] * N)) < min_diff)
        {
             
            // Update min_diff and res
            min_diff = Math.Abs(sum - (arr[i] * N));
            res = arr[i];
        }
    }
 
    // Print the resultant value
    Console.Write(res);
}
 
// Driver Code
public static void Main()
{
    int []arr = { 1, 2, 3, 4, 5 };
    int N = arr.Length;
     
    minimumDiff(arr, N);
}
}
 
// This code is contributed by subham348

# python 3 program for the above approach
 
# Function to find the element with
# minimum sum of differences between
# any elements in the array
def minimumDiff(arr, N):
   
    # Stores the required X and
    # sum of absolute differences
    res = arr[0]
    sum1 = 0
 
    # Calculate sum of array elements
    for i in range(N):
        sum1 += arr[i]
 
    # The sum of absolute differences
    # can't be greater than sum
    min_diff = sum1
 
    # Update res that gives
    # the minimum sum
    for i in range(N):
       
        # If the current difference
        # is less than the previous
        # difference
        if (abs(sum1 - (arr[i] * N)) < min_diff):
           
            # Update min_diff and res
            min_diff = abs(sum1 - (arr[i] * N))
            res = arr[i]
 
    # Print the resultant value
    print(res)
 
# Driver Code
if __name__ == '__main__':
    arr = [1, 2, 3, 4, 5]
    N = len(arr)
    minimumDiff(arr, N)
     
    # This code is contributed by SURENDRA_GANGWAR.

<script>
// Javascript program for the above approach
 
// Function to find the element with
// minimum sum of differences between
// any elements in the array
function minimumDiff(arr, N)
{
    // Stores the required X and
    // sum of absolute differences
    let res = arr[0], sum = 0;
 
    // Calculate sum of array elements
    for (let i = 0; i < N; i++)
        sum += arr[i];
 
    // The sum of absolute differences
    // can't be greater than sum
    let min_diff = sum;
 
    // Update res that gives
    // the minimum sum
    for (let i = 0; i < N; i++) {
 
        // If the current difference
        // is less than the previous
        // difference
        if (Math.abs(sum - (arr[i] * N))
            < min_diff) {
 
            // Update min_diff and res
            min_diff = Math.abs(sum - (arr[i] * N));
            res = arr[i];
        }
    }
 
    // Print the resultant value
    document.write(res);
}
 
// Driver Code
    let arr = [ 1, 2, 3, 4, 5 ];
    let N = arr.length;
    minimumDiff(arr, N);
 
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)