Maximizar el conteo de elementos que son estrictamente mayores en una subsecuencia que su promedio

Dada una array arr[] de tamaño N que contiene números enteros positivos, la tarea es encontrar la cantidad máxima de elementos que se pueden eliminar de la array usando cualquier cantidad de operaciones. En una operación, seleccione una subsecuencia de la array dada , tome su promedio y elimine los números que son estrictamente mayores que ese promedio de la array.

Ejemplo:

Entrada: arr[] = {1, 1, 3, 2, 4}
Salida: 3
Explicación:
Operación 1: Elija la subsecuencia {1, 2, 4}, promedio = (1+2+4)/3 = 2. Entonces arr[5]=4 se elimina. arr[]={1, 1, 3, 2}
Operación 2: Elija la subsecuencia {1, 3, 2}, promedio = (1+3+2)/3 = 2. Entonces arr[2]=3 se elimina . arr[]={1, 1, 2}
Operación 3: Elija la subsecuencia {1, 1}, promedio = (1+1)/2 = 1. Entonces arr[3]=2 se elimina. arr[]={1, 1}
No se pueden realizar más eliminaciones.

Entrada: arr[] = {5, 5, 5}
Salida: 0

Enfoque: el problema en este problema es que todos los elementos excepto el mínimo se pueden eliminar de la array porque si solo se usa el elemento mínimo para crear la subsecuencia, entonces su promedio es básicamente el mismo elemento y todos los demás elementos se pueden eliminar . Ahora, para resolver este problema, siga los pasos a continuación:

1. Encuentre la frecuencia del elemento mínimo, digamos freq .
2. Devuelva N-freq como la respuesta a este problema.

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

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum number of
// elements that can be deleted from the array
int elementsDeleted(vector<int>& arr)
{
 
    // Size of the array
    int N = arr.size();
 
    // Minimum element
    auto it = *min_element(arr.begin(), arr.end());
 
    // Finding frequency of minimum element
    int freq = 0;
    for (auto x : arr) {
        if (x == it)
            freq++;
    }
 
    return N - freq;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 3, 1, 1, 2, 4 };
    cout << elementsDeleted(arr);
}

// Java code for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the maximum number of
// elements that can be deleted from the array
static int elementsDeleted(int []arr)
{
 
    // Size of the array
    int N = arr.length;
 
    // Minimum element
    int it = Arrays.stream(arr).min().getAsInt();
 
    // Finding frequency of minimum element
    int freq = 0;
    for (int x : arr) {
        if (x == it)
            freq++;
    }
 
    return N - freq;
}
 
// Driver Code
public static void main(String[] args)
{
    int []arr = { 3, 1, 1, 2, 4 };
    System.out.print(elementsDeleted(arr));
}
}
 
// This code is contributed by 29AjayKumar

# Python code for the above approach
 
# Function to find the maximum number of
# elements that can be deleted from the array
def elementsDeleted(arr):
 
    # Size of the array
    N = len(arr)
 
    # Minimum element
    it = 10**9
 
    for i in range(len(arr)):
        it = min(it, arr[i])
 
    # Finding frequency of minimum element
    freq = 0
    for x in arr:
        if (x == it):
            freq += 1
    return N - freq
 
# Driver Code
arr = [3, 1, 1, 2, 4]
print(elementsDeleted(arr))
 
# This code is contributed by Saurabh jaiswal

// C# code for the above approach
using System;
using System.Linq;
class GFG {
 
    // Function to find the maximum number of
    // elements that can be deleted from the array
    static int elementsDeleted(int[] arr)
    {
 
        // Size of the array
        int N = arr.Length;
 
        // Minimum element
        int it = arr.Min();
 
        // Finding frequency of minimum element
        int freq = 0;
        foreach(int x in arr)
        {
            if (x == it)
                freq++;
        }
 
        return N - freq;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int[] arr = { 3, 1, 1, 2, 4 };
        Console.WriteLine(elementsDeleted(arr));
    }
}
 
// This code is contributed by ukasp.

<script>
      // JavaScript code for the above approach
 
      // Function to find the maximum number of
      // elements that can be deleted from the array
      function elementsDeleted(arr) {
 
          // Size of the array
          let N = arr.length;
 
          // Minimum element
          let it = Number.MAX_VALUE;
 
          for (let i = 0; i < arr.length; i++) {
              it = Math.min(it, arr[i]);
          }
 
          // Finding frequency of minimum element
          let freq = 0;
          for (let x of arr) {
              if (x == it)
                  freq++;
          }
 
          return N - freq;
      }
 
      // Driver Code
 
      let arr = [3, 1, 1, 2, 4];
      document.write(elementsDeleted(arr));
 
 
// This code is contributed by Potta Lokesh
  </script>

3

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