Número mínimo de elementos a sumar para hacer que la mediana sea igual a x

Una mediana en una array con la longitud de n es un elemento que ocupa la posición número (n+1)/2 después de ordenar los elementos en orden no decreciente (los elementos de la array se numeran comenzando con 1). La mediana de una array (2, 6, 1, 2, 3) es el número 2 y la mediana de una array (0, 96, 17, 23) es el número 17.

Ejemplos: 

Input : 3 10
        10 20 30
Output : 1
In the first sample we can add number 9 
to array (10, 20, 30). The resulting array
(9, 10, 20, 30) will have a median in 
position (4+1)/2 = 2, that is, 10

Input : 3 4
        1 2 3
Output : 4
In the second sample you should add numbers 
4, 5, 5, 5. The resulting array has median
equal to 4.

Primer enfoque: – El enfoque es agregar un número x más a la array hasta que la mediana de la array sea igual a x. A continuación se muestra la implementación del enfoque anterior: –

// C++ program to find minimum number
// of elements needs to add to the
// array so that its median equals x.
#include <bits/stdc++.h>
using namespace std;
 
// Returns count of elements to be
// added to make median x. This function
// assumes that a[] has enough extra space.
int minNumber(int a[], int n, int x)
{   
    // to sort the array in increasing order.
    sort(a, a + n);
 
    int k;
    for (k = 0; a[(n - 1) / 2] != x; k++) {
        a[n++] = x;
        sort(a, a + n);
    }
    return k;
}
 
// Driver code
main()
{
    int x = 10;
    int a[6] = { 10, 20, 30 };
    int n = 3;
    cout << minNumber(a, n, x) << endl;
    return 0;
}

// Java program to find minimum number
// of elements needs to add to the
// array so that its median equals x.
import java.util.Arrays;
 
class GFG
{
 
// Returns count of elements to be
// added to make median x. This function
// assumes that a[] has enough extra space.
static int minNumber(int a[], int n, int x)
{
    // to sort the array in increasing order.
    Arrays.sort(a);
 
    int k;
    for (k = 0; a[(n) / 2] != x; k++)
    {
        a[n++] = x;
        Arrays.sort(a);
    }
    return k;
}
 
// Driver code
public static void main(String[] args)
{
    int x = 10;
    int a[] = { 10, 20, 30 };
    int n = 3;
    System.out.println(minNumber(a, n-1, x));
}
}
 
// This code has been contributed by 29AjayKumar

# Python3 program to find minimum number
# of elements needs to add to the
# array so that its median equals x.
 
# Returns count of elements to be added 
# to make median x. This function
# assumes that a[] has enough extra space.
def minNumber(a, n, x):
     
    # to sort the array in increasing order.
    a.sort(reverse = False)
    k = 0
    while(a[int((n - 1) / 2)] != x):
        a[n - 1] = x
        n += 1
        a.sort(reverse = False)
        k += 1
 
    return k
 
# Driver code
if __name__ == '__main__':
    x = 10
    a = [10, 20, 30]
    n = 3
    print(minNumber(a, n, x))
 
# This code is contributed by
# Surendra_Gangwar

// C# program to find minimum number
// of elements needs to add to the
// array so that its median equals x.
using System;
 
class GFG
{
 
// Returns count of elements to be
// added to make median x. This function
// assumes that a[] has enough extra space.
static int minNumber(int []a, int n, int x)
{
    // to sort the array in increasing order.
    Array.Sort(a);
 
    int k;
    for (k = 0; a[(n) / 2] != x; k++)
    {
        a[n++] = x;
        Array.Sort(a);
    }
    return k;
}
 
// Driver code
public static void Main(String[] args)
{
    int x = 10;
    int []a = { 10, 20, 30 };
    int n = 3;
    Console.WriteLine(minNumber(a, n-1, x));
}
}
 
// This code contributed by Rajput-Ji

<?php
// PHP program to find minimum
// number of elements needs to
// add to the array so that its
// median equals x.
 
// Returns count of elements
// to be added to make median
// x. This function assumes
// that a[] has enough extra space.
function minNumber($a, $n, $x)
{
    // to sort the array in
    // increasing order.
    sort($a);
 
    $k;
    for ($k = 0;
         $a[($n - 1) / 2] != $x; $k++)
    {
        $a[$n++] = $x;
        sort($a);
    }
    return $k;
}
 
// Driver code
$x = 10;
$a = array (10, 20, 30);
$n = 3;
echo minNumber($a, $n, $x),"\n";
 
// This code is contributed by ajit
?>

<script>
    // Javascript program to find minimum number
    // of elements needs to add to the
    // array so that its median equals x.
     
    // Returns count of elements to be
    // added to make median x. This function
    // assumes that a[] has enough extra space.
    function minNumber(a, n, x)
    {   
     
        // to sort the array in increasing order.
        a.sort();
 
        let k;
        for (k = 0; a[parseInt((n - 1) / 2, 10)] != x; k++) {
            a[n++] = x;
            a.sort();
        }
        return k;
    }
 
    let x = 10;
    let a = [ 10, 20, 30 ];
    let n = 3;
    document.write(minNumber(a, n, x));
     
    // This code is contributed by mukesh07.
</script>

Producción : 

1

Complejidad temporal: O(kn Logn)
Espacio auxiliar: O(1)

Segundo enfoque: el mejor enfoque es contar todos los elementos iguales a x (es decir, e), mayores que x (es decir, h) y menores que x (es decir, l). Y entonces – 
si l es mayor que h entonces, la respuesta será (l – h) + 1 – e; 
Y si h es mayor que l entonces, ans será (h – l – 1) + 1 – e;
Podemos usar el esquema de partición de Hoare para contar elementos más pequeños, iguales y más grandes.

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

// C++ program to find minimum number of
// elements to add so that its median
// equals x.
#include <bits/stdc++.h>
using namespace std;
 
int minNumber(int a[], int n, int x)
{
    int l = 0, h = 0, e = 0;
    for (int i = 0; i < n; i++) {
 
        // no. of elements equals to x,
        // that is, e.
        if (a[i] == x)
            e++;
 
        // no. of elements greater than x,
        // that is, h.
        else if (a[i] > x)
            h++;
 
        // no. of elements smaller than x,
        // that is, l.
        else if (a[i] < x)
            l++;
    }
 
    int ans = 0;
    if (l > h)
        ans = l - h;
    else if (l < h)
        ans = h - l - 1;
     
    // subtract the no. of elements
    // that are equal to x.
    return ans + 1 - e;
}
 
// Driver code
int main()
{
    int x = 10;
    int a[] = { 10, 20, 30 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << minNumber(a, n, x) << endl;
    return 0;
}

// Java program to find minimum number
// of elements to add so that its
// median equals x.
import java.util.*;
import java.lang.*;
 
class GFG {
 
    public static int minNumber(int a[],
                           int n, int x)
    {
        int l = 0, h = 0, e = 0;
        for (int i = 0; i < n; i++)
        {
 
            // no. of elements equals to
            // x, that is, e.
            if (a[i] == x)
                e++;
 
            // no. of elements greater
            // than x, that is, h.
            else if (a[i] > x)
                h++;
 
            // no. of elements smaller
            // than x, that is, l.
            else if (a[i] < x)
                l++;
        }
 
        int ans = 0;
        if (l > h)
            ans = l - h;
        else if (l < h)
            ans = h - l - 1;
     
        // subtract the no. of elements
        // that are equal to x.
        return ans + 1 - e;
    }
 
    // Driven Program
    public static void main(String[] args)
    {
        int x = 10;
        int a[] = { 10, 20, 30 };
        int n = a.length;
        System.out.println(
                      minNumber(a, n, x));
    }
}
 
// This code is contributed by
// Prasad Kshirsagar

# Python3 program to find minimum number
# of elements to add so that its median
# equals x.
 
def minNumber (a, n, x):
    l = 0
    h = 0
    e = 0
    for i in range(n):
     
        # no. of elements equals to x,
        # that is, e.
        if a[i] == x:
            e+=1
         
        # no. of elements greater than x,
        # that is, h.
        elif a[i] > x:
            h+=1
         
        # no. of elements smaller than x,
        # that is, l.
        elif a[i] < x:
            l+=1
     
    ans = 0;
    if l > h:
        ans = l - h
    elif l < h:
        ans = h - l - 1;
     
    # subtract the no. of elements
    # that are equal to x.
    return ans + 1 - e
 
# Driver code
x = 10
a = [10, 20, 30]
n = len(a)
print(minNumber(a, n, x))
 
# This code is contributed
# by "Abhishek Sharma 44"

// C# program to find minimum
// number of elements to add
// so that its median equals x.
using System;
 
class GFG
{
public static int minNumber(int []a,
                            int n,
                            int x)
{
    int l = 0, h = 0, e = 0;
    for (int i = 0; i < n; i++)
    {
 
        // no. of elements
        // equals to x,
        // that is, e.
        if (a[i] == x)
            e++;
 
        // no. of elements
        // greater than x,
        // that is, h.
        else if (a[i] > x)
            h++;
 
        // no. of elements smaller
        // than x, that is, l.
        else if (a[i] < x)
            l++;
    }
 
    int ans = 0;
    if (l > h)
        ans = l - h;
    else if (l < h)
        ans = h - l - 1;
 
    // subtract the no.
    // of elements that
    // are equal to x.
    return ans + 1 - e;
}
 
// Driver Code
public static void Main()
{
    int x = 10;
    int []a = {10, 20, 30};
    int n = a.Length;
    Console.WriteLine(
                minNumber(a, n, x));
}
}
 
// This code is contributed
// by anuj_67.

<?php
// PHP program to find minimum
// number of elements to add so 
// that its median equals x.
 
function minNumber($a, $n, $x)
{
    $l = 0; $h = 0; $e = 0;
    for ($i = 0; $i < $n; $i++)
    {
 
        // no. of elements equals 
        // to x, that is, e.
        if ($a[$i] == $x)
            $e++;
 
        // no. of elements greater
        // than x, that is, h.
        else if ($a[$i] > $x)
            $h++;
 
        // no. of elements smaller
        // than x, that is, l.
        else if ($a[$i] < $x)
            $l++;
    }
 
    $ans = 0;
    if ($l > $h)
        $ans = $l - $h;
    else if ($l < $h)
        $ans = $h - $l - 1;
     
    // subtract the no. of elements
    // that are equal to x.
    return $ans + 1 - $e;
}
 
// Driver code
$x = 10;
$a = array (10, 20, 30);
$n = sizeof($a) ;
echo minNumber($a, $n, $x), "\n";
 
// This code is contributed by jit_t
?>

<script>
 
// Javascript program to find minimum number
// of elements to add so that its median
// equals x.
function minNumber(a, n, x)
{
    let l = 0, h = 0, e = 0;
    for(let i = 0; i < n; i++)
    {
         
        // No. of elements equals to x,
        // that is, e.
        if (a[i] == x)
            e++;
 
        // No. of elements greater than x,
        // that is, h.
        else if (a[i] > x)
            h++;
 
        // No. of elements smaller than x,
        // that is, l.
        else if (a[i] < x)
            l++;
    }
 
    let ans = 0;
    if (l > h)
        ans = l - h;
    else if (l < h)
        ans = h - l - 1;
 
    // Subtract the no. of elements
    // that are equal to x.
    return ans + 1 - e;
}
 
// Driver code
let x = 10;
let a = [ 10, 20, 30 ];
let n = a.length;
 
document.write(minNumber(a, n, x));
 
// This code is contributed by suresh07
 
</script>

Producción : 

1

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

Este artículo es una contribución de Sagar Shukla . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.