Operaciones mínimas de incremento/decremento requeridas para hacer Median as X

Dada una array A[] de n enteros impares y un entero X . Calcule el número mínimo de operaciones requeridas para hacer que la mediana de la array sea igual a X, donde, en una operación, podemos aumentar o disminuir cualquier elemento en uno.

Ejemplos: 

Entrada: A[] = {6, 5, 8}, X = 8 
Salida: 2 
Explicación: 
Aquí 6 se puede aumentar dos veces. La array se convertirá en 8, 5, 8, que se convierte en 5, 8, 8 después de ordenar, por lo que la mediana es igual a 8.

Entrada: A[] = {1, 4, 7, 12, 3, 5, 9}, X = 5 
Salida: 0 
Explicación: 
Después de ordenar, 5 está en la posición media, por lo que se requieren 0 pasos. 
 

Enfoque: la idea de cambiar la mediana de la array será ordenar la array dada . Luego, después de ordenar, el mejor candidato posible para hacer la mediana es el elemento del medio porque será mejor reducir los números antes del elemento del medio, ya que son más pequeños, y aumentar los números después del elemento del medio, ya que son más grandes.

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

// C++ implementation to determine the
// Minimum numbers of steps to make
// median of an array equal X
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count minimum
// required operations to
// make median X
int count(vector<int> a, int X)
{
    // Sorting the array a[]
    sort(a.begin(), a.end());
    int ans = 0;
 
    // Calculate the size of array
    int n = a.size();
 
    // Iterate over the array
    for (int i = 0; i < n; i++) {
        // For all elements
        // less than median
        if (i < n / 2)
            ans += max(0, a[i] - X);
 
        // For element equal
        // to median
        else if (i == n / 2)
            ans += abs(X - a[i]);
 
        // For all elements
        // greater than median
        else
            ans += max(0, X - a[i]);
    }
 
    // Return the answer
    return ans;
}
 
// Driver code
int main()
{
    vector<int> a = { 6, 5, 8 };
    int X = 8;
    cout << count(a, X) << "\n";
    return 0;
}

// Java implementation to determine the
// Minimum numbers of steps to make
// median of an array equal X
import java.util.*;
 
class GFG{
 
// Function to count minimum
// required operations to
// make median X
static int count(int[] a, int X)
{
     
    // Sorting the array a[]
    Arrays.sort(a);
    int ans = 0;
 
    // Calculate the size of array
    int n = a.length;
 
    // Iterate over the array
    for(int i = 0; i < n; i++)
    {
        
       // For all elements
       // less than median
       if (i < n / 2)
           ans += Math.max(0, a[i] - X);
        
       // For element equal
       // to median
       else if (i == n / 2)
           ans += Math.abs(X - a[i]);
       
       // For all elements
       // greater than median
       else
           ans += Math.max(0, X - a[i]);
    }
     
    // Return the answer
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int []a = { 6, 5, 8 };
    int X = 8;
     
    System.out.print(count(a, X) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

# Python3 implementation to determine the
# Minimum numbers of steps to make
# median of an array equal X
 
# Function to count minimum
# required operations to
# make median X
def count(a, X):
 
    # Sorting the array a[]
    a.sort()
    ans = 0
 
    # Calculate the size of array
    n = len(a)
 
    # Iterate over the array
    for i in range(n):
         
        # For all elements
        # less than median
        if (i < n // 2):
            ans += max(0, a[i] - X)
 
        # For element equal
        # to median
        elif (i == n // 2):
            ans += abs(X - a[i])
 
        # For all elements
        # greater than median
        else:
            ans += max(0, X - a[i]);
 
    # Return the answer
    return ans
 
# Driver code
a = [ 6, 5, 8 ]
X = 8
 
print(count(a, X))
 
# This code is contributed by divyeshrabadiya07

// C# implementation to determine the
// Minimum numbers of steps to make
// median of an array equal X
using System;
 
class GFG{
 
// Function to count minimum
// required operations to
// make median X
static int count(int[] a, int X)
{
     
    // Sorting the array []a
    Array.Sort(a);
    int ans = 0;
 
    // Calculate the size of array
    int n = a.Length;
 
    // Iterate over the array
    for(int i = 0; i < n; i++)
    {
        
       // For all elements
       // less than median
       if (i < n / 2)
           ans += Math.Max(0, a[i] - X);
            
       // For element equal
       // to median
       else if (i == n / 2)
           ans += Math.Abs(X - a[i]);
        
       // For all elements
       // greater than median
       else
           ans += Math.Max(0, X - a[i]);
    }
     
    // Return the answer
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = { 6, 5, 8 };
    int X = 8;
     
    Console.Write(count(a, X) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// Javascript implementation to determine the
// Minimum numbers of steps to make
// median of an array equal X
 
// Creating the bblSort function
function bblSort(arr)
{
    for(var i = 0; i < arr.length; i++)
    {
     
        // Last i elements are already in place 
        for(var j = 0; j < (arr.length - i - 1); j++)
        {
         
            // Checking if the item at present
            // iteration is greater than the
            // next iteration
            if (arr[j] > arr[j+1])
            {
             
                // If the condition is true
                // then swap them
                var temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
     
    // Return the sorted array
    return (arr);
}
 
// Function to count minimum
// required operations to
// make median X
function count(a, X)
{
     
    // Sorting the array a
    a  = bblSort(a);
    var ans = 0;
 
    // Calculate the size of array
    var n = a.length;
 
    // Iterate over the array
    for(i = 0; i < n; i++)
    {
         
        // For all elements
        // less than median
        if (i < parseInt(n / 2))
            ans += Math.max(0, a[i] - X);
 
        // For element equal
        // to median
        else if (i == parseInt(n / 2))
            ans += Math.abs(X - a[i]);
 
        // For all elements
        // greater than median
        else
            ans += Math.max(0, X - a[i]);
    }
     
    // Return the answer
    return ans;
}
 
// Driver code
var a = [ 6, 5, 8 ];
var X = 8;
 
document.write(count(a, X));
 
// This code is contributed by aashish1995
 
</script>

2

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