Cuente el número máximo de elementos que se pueden seleccionar de la array

Dada una array arr[] , la tarea es contar el número máximo de elementos que se pueden seleccionar de la array dada siguiendo el siguiente proceso de selección: 

• En la primera selección, seleccione un elemento que sea mayor o igual a 1.
• En la segunda selección, seleccione un elemento que sea mayor o igual a 2.
• En la tercera selección, seleccione un elemento que sea mayor o igual a 3 y así sucesivamente.

Un elemento solo se puede seleccionar una vez. La operación se detiene cuando no es posible seleccionar ningún elemento. Entonces, la tarea es maximizar el conteo de selección de la array.

Ejemplos: 

Entrada: arr[] = { 4, 1, 3, 1 } 
Salida: 3 
1.ª selección: 1 se selecciona como 1 >= 1. 
2.ª selección: 3 se selecciona como 3 >= 2. 
3.ª selección: 4 se selecciona como 4 >= 3. 
No son posibles más selecciones. Por lo tanto, la respuesta es 3. 

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

Enfoque: Para maximizar el conteo de selección, es necesario seleccionar primero los números más pequeños posibles y luego los números más grandes si la selección no es posible. Esto se puede hacer fácilmente ordenando la array. Ahora, recorra la array e incremente el resultado en 1 cuando el elemento sea mayor o igual que el número a seleccionar para la operación actual.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum count of
// selection possible from the given array
// following the given process
int maxSelectionCount(int a[], int n)
{
    // Initialize result
    int res = 0;
 
    // Sorting the array
    sort(a, a + n);
 
    // Initialize the select variable
    int select = 1;
 
    // Loop through array
    for (int i = 0; i < n; i++) {
        // If selection is possible
        if (a[i] >= select) {
            res++; // Increment result
            select++; // Increment selection variable
        }
    }
 
    return res;
}
 
// Driver Code
int main()
{
    int arr[] = { 4, 2, 1, 3, 5, 1, 4 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << maxSelectionCount(arr, N);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
    // Function to return the maximum count of
    // selection possible from the given array
    // following the given process
    static int maxSelectionCount(int a[], int n)
    {
        // Initialize result
        int res = 0;
 
        // Sorting the array
        Arrays.sort(a);
 
        // Initialize the select variable
        int select = 1;
 
        // Loop through array
        for (int i = 0; i < n; i++)
        {
            // If selection is possible
            if (a[i] >= select)
            {
                res++; // Increment result
                select++; // Increment selection variable
            }
        }
 
        return res;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = {4, 2, 1, 3, 5, 1, 4};
 
        int N = arr.length;
 
        System.out.println(maxSelectionCount(arr, N));
    }
}
 
// This code contributed by Rajput-Ji

# Python implementation of the approach
 
# Function to return the maximum count of
# selection possible from the given array
# following the given process
def maxSelectionCount(a, n):
    # Initialize result
    res = 0;
 
    # Sorting the array
    a.sort();
 
    # Initialize the select variable
    select = 1;
 
    # Loop through array
    for i in range(n):
        # If selection is possible
        if (a[i] >= select):
            res += 1; # Increment result
            select += 1; # Increment selection variable
 
    return res;
 
 
# Driver Code
arr = [ 4, 2, 1, 3, 5, 1, 4 ];
N = len(arr);
print(maxSelectionCount(arr, N));
 
# This code contributed by PrinciRaj1992

// C# implementation of the approach
using System;
 
class GFG
{
    // Function to return the maximum count of
    // selection possible from the given array
    // following the given process
    static int maxSelectionCount(int []a, int n)
    {
        // Initialize result
        int res = 0;
 
        // Sorting the array
        Array.Sort(a);
 
        // Initialize the select variable
        int select = 1;
 
        // Loop through array
        for (int i = 0; i < n; i++)
        {
            // If selection is possible
            if (a[i] >= select)
            {
                res++; // Increment result
                select++; // Increment selection variable
            }
        }
 
        return res;
    }
 
    // Driver Code
    public static void Main()
    {
        int []arr = {4, 2, 1, 3, 5, 1, 4};
 
        int N = arr.Length;
 
        Console.WriteLine(maxSelectionCount(arr, N));
    }
}
 
// This code contributed by AnkitRai01

<script>
 
// Javascript implementation of the approach
 
// Function to return the maximum count of
// selection possible from the given array
// following the given process
function maxSelectionCount(a, n)
{
     
    // Initialize result
    var res = 0;
 
    // Sorting the array
    a.sort();
 
    // Initialize the select variable
    var select = 1;
 
    // Loop through array
    for(var i = 0; i < n; i++)
    {
         
        // If selection is possible
        if (a[i] >= select)
        {
            // Increment result
            res++;
             
            // Increment selection variable
            select++;
        }
    }
    return res;
}
 
// Driver Code
var arr = [ 4, 2, 1, 3, 5, 1, 4 ];
var N = arr.length;
 
document.write(maxSelectionCount(arr, N));
 
// This code is contributed by rrrtnx
 
</script>

5

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