Minimizar el valor de x que minimiza el valor de |a1−x|^c+|a2−x|^c+···+|an−x|^c para el valor de c como 1 y 2

Dada una array arr[] de N elementos, la tarea es encontrar el valor de x que minimice el valor de expresión para c = 1.

|a ₁ −x| ^c +|a ₂ −x| ^c +···+|a _n −x| ^c   = |a ₁ −x|+|a ₂ −x|+···+|a _n −x|

Ejemplos:

Entrada : arr[] = { 1, 2, 9, 2, 6 }  
Salida : 2
Explicación : la mejor solución es seleccionar x = 2 que produce la suma |1−2| + |2−2| + |9−2| + |2−2| + |6−2| = 12 , que es la suma mínima posible, para todos los demás valores, la suma así obtenida será mayor que 2

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

Enfoque : En el caso general, la mejor opción para x es la mediana de los números dados . La mediana es una opción óptima, porque si x es menor que la mediana, la suma se vuelve más pequeña al aumentar x , y si x es mayor que la mediana, la suma se vuelve más pequeña al disminuir x . Por tanto, la solución óptima es que x sea la mediana. 

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 print the possible
// values of x that minimizes the sum
void findX(int arr[], int n)
{
    // Sort the numbers
    sort(arr, arr + n);
 
    // Stores the median
    int x;
 
    // Only one median if n is odd
    if (n % 2 != 0) {
        x = arr[n / 2];
    }
 
    // Two medians if n is even
    // and every value between them
    // is optimal print any of them
    else {
        int a = arr[n / 2 - 1];
        int b = arr[n / 2];
        x = a;
    }
 
    int sum = 0;
 
    // Find minimum sum
    for (int i = 0; i < n; i++) {
        sum += abs(arr[i] - x);
    }
 
    cout << sum;
}
 
// Driver Code
int main()
{
    int arr1[] = { 1, 2, 9, 2, 6 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
 
    findX(arr1, n1);
    return 0;
}

// Java code for the above approach
import java.util.*;
 
class GFG
{
   
  // Function to print the possible
// values of x that minimizes the sum
static void findX(int arr[], int n)
{
   
    // Sort the numbers
    Arrays.sort(arr);
 
    // Stores the median
    int x;
 
    // Only one median if n is odd
    if (n % 2 != 0) {
        x = arr[(int)Math.floor(n / 2)];
    }
 
    // Two medians if n is even
    // and every value between them
    // is optimal print any of them
    else {
        int a = arr[n / 2 - 1];
        int b = arr[n / 2];
        x = a;
    }
 
    int sum = 0;
 
    // Find minimum sum
    for (int i = 0; i < n; i++) {
        sum += Math.abs(arr[i] - x);
    }
 
   System.out.println( sum);
}
 
    public static void main (String[] args) {
         
    int arr1[] = { 1, 2, 9, 2, 6 };
    int n1 = arr1.length;
 
    findX(arr1, n1);
    }
}
 
// This code is contributed by Potta Lokesh

# Python program for the above approach
 
# Function to print the possible
# values of x that minimizes the sum
def findX(arr, n):
   
  # Sort the numbers
  arr.sort();
 
  # Stores the median
  x = None;
 
  # Only one median if n is odd
  if (n % 2 != 0):
    x = arr[n // 2];
   
  # Two medians if n is even
  # and every value between them
  # is optimal print any of them
  else:
    a = arr[(n // 2) - 1];
    b = arr[n // 2];
    x = a;
  sum = 0;
 
  # Find minimum sum
  for i in range(n):
    sum += abs(arr[i] - x);
 
 
  print(sum);
 
# Driver Code
arr1 = [1, 2, 9, 2, 6];
n1 = len(arr1)
 
findX(arr1, n1);
 
# This code is contributed by gfgking.

// C# code for the above approach
using System;
 
class GFG {
 
    // Function to print the possible
    // values of x that minimizes the sum
    static void findX(int[] arr, int n)
    {
 
        // Sort the numbers
        Array.Sort(arr);
 
        // Stores the median
        int x;
 
        // Only one median if n is odd
        if (n % 2 != 0) {
            x = arr[(int)Math.Floor((float)(n / 2))];
        }
 
        // Two medians if n is even
        // and every value between them
        // is optimal print any of them
        else {
            int a = arr[n / 2 - 1];
 
            x = a;
        }
 
        int sum = 0;
 
        // Find minimum sum
        for (int i = 0; i < n; i++) {
            sum += Math.Abs(arr[i] - x);
        }
 
        Console.WriteLine(sum);
    }
 
    public static void Main(string[] args)
    {
 
        int[] arr1 = { 1, 2, 9, 2, 6 };
        int n1 = arr1.Length;
 
        findX(arr1, n1);
    }
}
 
// This code is contributed by ukasp.

<script>
// Javascript program for the above approach
 
// Function to print the possible
// values of x that minimizes the sum
function findX(arr, n) {
  // Sort the numbers
  arr.sort((a, b) => a - b);
 
  // Stores the median
  let x;
 
  // Only one median if n is odd
  if (n % 2 != 0) {
    x = arr[Math.floor(n / 2)];
  }
 
  // Two medians if n is even
  // and every value between them
  // is optimal print any of them
  else {
    let a = arr[Math.floor(n / 2) - 1];
    let b = arr[Math.floor(n / 2)];
    x = a;
  }
 
  let sum = 0;
 
  // Find minimum sum
  for (let i = 0; i < n; i++) {
    sum += Math.abs(arr[i] - x);
  }
 
  document.write(sum);
}
 
// Driver Code
 
let arr1 = [1, 2, 9, 2, 6];
let n1 = arr1.length;
 
findX(arr1, n1);
 
// This code is contributed by gfgking.
</script>

12

Complejidad de tiempo : O(N*log N)
Espacio auxiliar : O(1)

Dada una array arr[] de N elementos, la tarea es encontrar el valor de x que minimice el valor de expresión para c = 2 .

|a ₁ −x| ^c +|a ₂ −x| ^c +···+|a _n −x| ^c   = (un ₁ −x) ² +(un ₂ −x) ² +···+(un norte _−x ) ² .

Ejemplos:

Entrada : arr[] = { 1, 2, 9, 2, 6 }  
Salida : 4
Explicación : la mejor solución es seleccionar x = 4 que produce la suma (1−4)^2 + (2−4)^2 + (9−4)^2 + (2−4)^2 + (6−4)^2 = 46, que es la suma mínima posible.

Entrada : arr[] = { 1, 2, 2, 4, 6 }  
Salida : 3

Enfoque : En el caso general, la mejor opción para x es el promedio de los números . Este resultado se puede derivar expandiendo la suma de la siguiente manera:

nx ² −2x(a ₁ +a ₂ +···+a _n ) + (a ₁ ² +a ₂ ² +···+a _n ² ) 

La última parte no depende de x . Las partes restantes forman una función nx ² − 2xs donde s=a ₁ +a ₂ +···+a _n . Aplicando la derivada a esta ecuación wrt x e igualando el resultado a cero nos da x = s / n , que es el valor que minimiza la suma.
 

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

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the value of x
// that minimizes the sum
void findX(int arr[], int n)
{
    // Store the sum
    double sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
 
    // Store the average of numbers
    double x = sum / n;
 
    double minSum = 0;
 
    // Find minimum sum
    for (int i = 0; i < n; i++) {
        minSum += pow((arr[i] - x), 2);
    }
 
    cout << minSum;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 9, 2, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    findX(arr, n);
 
    return 0;
}

// Java implementation for the above approach
import java.util.*;
public class GFG
{
// Function to find the value of x
// that minimizes the sum
static void findX(int []arr, int n)
{
    // Store the sum
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
 
    // Store the average of numbers
    int x = sum / n;
 
    int minSum = 0;
 
    // Find minimum sum
    for (int i = 0; i < n; i++) {
        minSum += Math.pow((arr[i] - x), 2);
    }
 
    System.out.print(minSum);
}
 
// Driver Code
public static void main(String args[])
{
    int []arr = { 1, 2, 9, 2, 6 };
    int n = arr.length;
 
    findX(arr, n);
}
}
// This code is contributed by Samim Hossain Mondal.

# Python implementation for the above approach
 
# Function to find the value of x
# that minimizes the sum
def findX(arr, n):
   
    # Store the sum
    sum = 0;
    for i in range(n):
        sum += arr[i];
     
    # Store the average of numbers
    x = sum // n;
 
    minSum = 0;
 
    # Find minimum sum
    for i in range(n):
        minSum += pow((arr[i] - x), 2);
    print(minSum);
 
# Driver Code
if __name__ == '__main__':
    arr = [ 1, 2, 9, 2, 6 ];
    n = len(arr);
 
    findX(arr, n);
 
# This code is contributed by shikhasingrajput

// C# implementation for the above approach
using System;
class GFG
{
// Function to find the value of x
// that minimizes the sum
static void findX(int []arr, int n)
{
    // Store the sum
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
 
    // Store the average of numbers
    int x = sum / n;
 
    int minSum = 0;
 
    // Find minimum sum
    for (int i = 0; i < n; i++) {
        minSum += (int)Math.Pow((arr[i] - x), 2);
    }
 
    Console.Write(minSum);
}
 
// Driver Code
public static void Main()
{
    int []arr = { 1, 2, 9, 2, 6 };
    int n = arr.Length;
 
    findX(arr, n);
}
}
// This code is contributed by Samim Hossain Mondal.

<script>
// Javascript implementation for the above approach
 
// Function to find the value of x
// that minimizes the sum
function findX(arr, n)
{
    // Store the sum
    let sum = 0;
    for (let i = 0; i < n; i++) {
        sum += arr[i];
    }
 
    // Store the average of numbers
    let x = sum / n;
 
    let minSum = 0;
 
    // Find minimum sum
    for (let i = 0; i < n; i++) {
        minSum += Math.pow((arr[i] - x), 2);
    }
 
    document.write(minSum);
}
 
// Driver Code
let arr = [ 1, 2, 9, 2, 6 ];
let n = arr.length;
 
findX(arr, n);
 
// This code is contributed by Samim Hossain Mondal.
</script>

46

Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)