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:
- Para el elemento arr[0](= 1): |(1 – 1)| + |(2 – 1)| + |(3 – 1)| + |(4 – 1)| + |(5 – 1)| = 0 + 1 + 2 + 3 + 4 = 10.
- Para el elemento arr[1](= 2): |(1 – 2)| + |(2 – 2)| + |(3 – 2)| + |(4 – 2)| + |(5 – 2)| = 1 + 0 + 1 + 2 + 3 = 7.
- Para el elemento arr[2](= 3): |(1 – 3)| + |(2 – 3)| + |(3 – 3)| + |(4 – 3)| + |(5 – 3)| = 2 + 1 + 0 + 1 + 2 = 6.
- Para el elemento arr[3](= 4): |(1 – 4)| + |(2 – 4)| + |(3 – 4)| + |(4 – 4)| + |(5 – 4)| = 3 + 2 + 1 + 0 + 1 = 7.
- 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 2 )
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++
// 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
// 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#
// 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
Python3
# 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.
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por subhammahato348 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA