Número máximo de elementos mayores que X después de distribuir equitativamente el subconjunto de la array

Dada una array, arr[] y un entero X , la tarea es contar el número de elementos mayores que X después de dividir equitativamente el subconjunto de elementos. Es decir, cada elemento del subconjunto será igual a 

Ejemplos: 

Entrada: arr[] = {5, 1, 2, 1}, X = 3 
Salida: 2 
Explicación: 
el subconjunto que se distribuye por igual es {5, 2}. 
Después de lo cual los elementos serán 3,5 cada uno. 
Array => {3.5, 1, 3.5, 1} 
Número total de elementos mayores que X = 2

Entrada: arr[] = {3, 4, 5}, X = 6 
Salida: 0 
Explicación: 
No hay forma de distribuir ningún subconjunto de la array para que los elementos sean mayores que 6. 
 

Enfoque: la idea es ordenar la array e incluir los elementos más grandes de la array de modo que su promedio sea mayor o igual a X. El recuento de los elementos cuyo promedio es mayor o igual a X es el subconjunto deseado que puede ser igualmente dividido y cada elemento es mayor que X.

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

// C++ implementation to find the
// maximum number of elements greater
// than X by equally distributing
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the
// maximum number of elements greater
// than X by equally distributing
void redistribute(int arr[], int n, int x)
{
    // Sorting the array
    sort(arr, arr + n, greater<int>());
 
    int i, sum = 0;
 
    // Loop to iterate over the elements
    // of the array
    for (i = 0; i < n; i++) {
        sum += arr[i];
 
        // If no more elements can
        // become larger than x
        if (sum / (i + 1) < x) {
            cout << i << endl;
            break;
        }
    }
    if (i == n)
        cout << n << endl;
}
 
// Driver Code
int main()
{
    int arr[] = { 5, 1, 2, 1 };
    int x = 3;
    redistribute(arr, 4, x);
    return 0;
}

// Java implementation to find the
// maximum number of elements greater
// than X by equally distributing
import java.util.*;
 
class GFG{
 
// Function to find the maximum
// number of elements greater
// than X by equally distributing
static void redistribute(Integer arr[], int n,
                                        int x)
{
     
    // Sorting the array
    Arrays.sort(arr, Collections.reverseOrder());
 
    int i, sum = 0;
 
    // Loop to iterate over the elements
    // of the array
    for(i = 0; i < n; i++)
    {
       sum += arr[i];
        
       // If no more elements can
       // become larger than x
       if (sum / (i + 1) < x)
       {
           System.out.print(i + "\n");
           break;
       }
    }
    if (i == n)
        System.out.print(n + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
    Integer arr[] = { 5, 1, 2, 1 };
    int x = 3;
     
    redistribute(arr, 4, x);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation to find the
# maximum number of elements greater
# than X by equally distributing
 
# Function to find the
# maximum number of elements greater
# than X by equally distributing
def redistribute(arr, n, x):
 
    # Sorting the array
    arr.sort(reverse = True)
 
    sum = 0
 
    # Loop to iterate over the
    # elements of the array
    for i in range(n):
        sum += arr[i]
 
        # If no more elements can
        # become larger than x
        if (sum / (i + 1) < x):
            print(i)
            break
         
    if (i == n):
        print(n)
 
# Driver Code
arr = [ 5, 1, 2, 1 ]
x = 3
 
# Function call
redistribute(arr, 4, x)
 
# This code is contributed by Vishal Maurya.

// C# implementation to find the
// maximum number of elements greater
// than X by equally distributing
using System;
 
class GFG{
 
// Function to find the maximum
// number of elements greater
// than X by equally distributing
static void redistribute(int []arr, int n,
                                    int x)
{
     
    // Sorting the array
    Array.Sort(arr);
    Array.Reverse(arr);
 
    int i, sum = 0;
 
    // Loop to iterate over the elements
    // of the array
    for(i = 0; i < n; i++)
    {
       sum += arr[i];
        
       // If no more elements can
       // become larger than x
       if (sum / (i + 1) < x)
       {
           Console.Write(i + "\n");
           break;
       }
    }
    if (i == n)
        Console.Write(n + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 5, 1, 2, 1 };
    int x = 3;
     
    redistribute(arr, 4, x);
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript implementation to find the
// maximum number of elements greater
// than X by equally distributing
 
// Function to find the maximum
// number of elements greater
// than X by equally distributing
function redistribute(arr, n, x)
{
     
    // Sorting the array
    arr.sort();
    arr.reverse();
   
    let i, sum = 0;
   
    // Loop to iterate over the elements
    // of the array
    for(i = 0; i < n; i++)
    {
        sum += arr[i];
         
        // If no more elements can
        // become larger than x
        if ((sum / (i + 1)) < x)
        {
            document.write(i );
            break;
        }
    }
    if (i == n)
        document.write(n);
}
  
// Driver Code
let arr = [ 5, 1, 2, 1 ];
let x = 3;
   
redistribute(arr, 4, x);
 
// This code is contributed by sanjoy_62
 
</script>

2

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