Maximum value K such that array has at-least K elements that are >= K - GeeksforGeeks

Maximum value K such that array has at-least K elements that are >= K - GeeksforGeeks
Given an array of positive integers, find maximum possible value K such that the array has at-least K elements that are greater than or equal to K. The array is unsorted and may contain duplicate values.

Method 2 [Efficient : O(n) time and O(n) extra space]
1) The idea is to construct axillary array of size n + 1, and use that array to find count of greater elements in input array. Let the auxiliary array be freq[]. We initialize all elements of this array as 0.

2) We process all input elements.
        a) If an element arr[i] is less than n, then we increment its frequency, i.e., we do freq[arr[i]]++.
        b) Else we increment freq[n].

3) After step 2 we have two things.
        a) Frequencies of elements for elements smaller than n stored in freq[0..n-1].
        b) Count of elements greater than n stored in freq[n].

Finally, we process the freq[] array backwards to find the output by keeping sum of the values processed so far.

int findMaximumNum(unsigned int arr[], int n)

{

    // construct axillary array of size n + 1 and

    // initialize the array with 0

    vector<int> freq(n+1, 0);

 

    // store the frequency of elements of

    // input array in the axillary array

    for (int i = 0; i < n; i++)

    {

        // If element is smaller than n, update its

        // frequency

        if (arr[i] < n)

            freq[arr[i]]++;

 

        // Else increment count of elements greater

        // than n.

        else

            freq[n]++;

    }

 

    // sum stores number of elements in input array

    // that are greater than or equal to current

    // index

    int sum = 0;

 

    // scan auxillary array backwards

    for (int i = n; i > 0; i--)

    {

        sum += freq[i];

 

        // if sum is greater than current index,

        // current index is the answer

        if (sum >= i)

            return i;

    }

}

int findMaximumNum(unsigned int arr[], int n)

{

    // output can contain any number from n to 0

    // where n is length of the array

 

    // We start a loop from n as we need to find

    // maximum possible value

    for (int i = n; i >= 1; i--)

    {

        // count contains total number of elements

        // in input array that are more than equal to i

        int count = 0;

 

        // traverse the input array and find count

        for (int j=0; j<n; j++)

            if (i <= arr[j])

                count++;

 

        if (count >= i)

          return i;

    }   

    return 1;

}

Read full article from Maximum value K such that array has at-least K elements that are >= K - GeeksforGeeks