Encuentre el punto en el eje X de N puntos dados que tienen la menor Suma de distancias de todos los demás puntos

Dada una array arr[] que consta de N enteros, que denotan N puntos que se encuentran en el eje X , la tarea es encontrar el punto que tiene la menor suma de distancias desde todos los demás puntos.

Ejemplo:

Entrada: arr[] = {4, 1, 5, 10, 2} 
Salida: (4, 0) 
Explicación: 
Distancia de 4 desde el resto de los elementos = |4 – 1| + |4 – 5| + |4 – 10| + |4 – 2| = 12 
Distancia de 1 al resto de los elementos = |1 – 4| + |1 – 5| + |1 – 10| + |1 – 2| = 17 
Distancia de 5 al resto de los elementos = |5 – 1| + |5 – 4| + |5 – 2| + |5 – 10| = 13 
Distancia de 10 al resto de los elementos = |10 – 1| + |10 – 2| + |10 – 5| + |10 – 4| = 28 
Distancia de 2 al resto de los elementos = |2 – 1| + |2 – 4| + |2 – 5| + |2 – 10| = 14
Entrada: arr[] = {3, 5, 7, 10} 
Salida: 5 
 

Enfoque ingenuo: 
la tarea es iterar sobre la array y, para cada elemento de la array, calcular la suma de su diferencia absoluta con todos los demás elementos de la array. Finalmente, imprima el elemento de array con la suma máxima de diferencias. 
Complejidad de Tiempo: O(N ² ) 
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es encontrar la mediana de la array. La mediana de la array tendrá la menor distancia total posible de otros elementos de la array. Para una array con un número par de elementos, hay dos medianas posibles y ambas tendrán la misma distancia total, devuelve la que tiene el índice más bajo ya que está más cerca del origen.

Siga los pasos a continuación para resolver el problema:

• Ordenar la array dada.
• Si N es impar , devuelve el elemento (N + 1/2) ^ésimo .
• De lo contrario, devuelva el (N / 2) ^th elemento.

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find median of the array
int findLeastDist(int A[], int N)
{
    // Sort the given array
    sort(A, A + N);
 
    // If number of elements are even
    if (N % 2 == 0) {
 
        // Return the first median
        return A[(N - 1) / 2];
    }
 
    // Otherwise
    else {
        return A[N / 2];
    }
}
 
// Driver Code
int main()
{
 
    int A[] = { 4, 1, 5, 10, 2 };
    int N = sizeof(A) / sizeof(A[0]);
    cout << "(" << findLeastDist(A, N)
         << ", " << 0 << ")";
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to find median of the array
static int findLeastDist(int A[], int N)
{
     
    // Sort the given array
    Arrays.sort(A);
 
    // If number of elements are even
    if (N % 2 == 0)
    {
         
        // Return the first median
        return A[(N - 1) / 2];
    }
 
    // Otherwise
    else
    {
        return A[N / 2];
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 4, 1, 5, 10, 2 };
    int N = A.length;
     
    System.out.print("(" + findLeastDist(A, N) +
                    ", " + 0 + ")");
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program to implement
# the above approach
 
# Function to find median of the array
def findLeastDist(A, N):
     
    # Sort the given array
    A.sort();
 
    # If number of elements are even
    if (N % 2 == 0):
 
        # Return the first median
        return A[(N - 1) // 2];
 
    # Otherwise
    else:
        return A[N // 2];
 
# Driver Code
A = [4, 1, 5, 10, 2];
N = len(A);
 
print("(" , findLeastDist(A, N),
      ", " , 0 , ")");
 
# This code is contributed by PrinciRaj1992

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to find median of the array
static int findLeastDist(int []A, int N)
{
     
    // Sort the given array
    Array.Sort(A);
 
    // If number of elements are even
    if (N % 2 == 0)
    {
         
        // Return the first median
        return A[(N - 1) / 2];
    }
 
    // Otherwise
    else
    {
        return A[N / 2];
    }
}
 
// Driver Code
public static void Main(string[] args)
{
    int []A = { 4, 1, 5, 10, 2 };
    int N = A.Length;
     
    Console.Write("(" + findLeastDist(A, N) +
                 ", " + 0 + ")");
}
}
 
// This code is contributed by rutvik_56

<script>
 
// Javascript Program to implement
// the above approach
 
// Function to find median of the array
function findLeastDist(A, N)
{
    // Sort the given array
    A.sort((a,b) => a-b);
 
    console.log(A);
     
    // If number of elements are even
    if ((N % 2) == 0) {
 
        // Return the first median
        return A[parseInt((N - 1) / 2)];
    }
 
    // Otherwise
    else {
        return A[parseInt(N / 2)];
    }
}
 
// Driver Code
var A = [ 4, 1, 5, 10, 2 ];
var N = A.length;
document.write( "(" + findLeastDist(A, N)
     + ", " + 0 + ")");
 
</script>

(4, 0)

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