Given an array Arr of N positive integers. Find the maximum possible value of K such that the array has at-least K elements that are greater than or equal to K.
Example 1:
Input:
N = 6
Arr[] = {2, 3, 4, 5, 6, 7}
Output: 4
Explanation: 4 elements [4, 5, 6, 7] 
are greater than equal to 4.
Example 2:
Input:
N = 4
Arr[] = {1, 2, 3, 4}
Output: 2
Explanation: 3 elements [2, 3, 4] are 
greater than equal to 2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findMaximumNum() which takes the array of integers arr and its size n as input parameters and returns an integer denoting the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
2 <= N <= 10^{5}
0 <= Arr[i] <= 10^{6}
The array is unsorted and may contain duplicate values.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def findMaximumNum(self, arr, n):

        # code here

Solutions:
class Solution:

	def findMaximumNum(self, arr, n):
		arr.sort()
		if arr.count(1) == n:
			return 1
		for i in arr:
			if i >= n:
				break
			else:
				n -= 1
		return n


class Solution:

	def findMaximumNum(self, arr, n):
		arr.sort(reverse=True)
		while len(arr) > arr[-1]:
			arr.pop()
		return len(arr)


class Solution:

	def findMaximumNum(self, arr, n):
		freq = [0 for i in range(n + 1)]
		for i in range(n):
			if arr[i] < n:
				freq[arr[i]] += 1
			else:
				freq[n] += 1
		summ = 0
		for i in range(n, 0, -1):
			summ += freq[i]
			if summ >= i:
				return i


class Solution:

	def findMaximumNum(self, arr, n):
		arr.sort()
		l = 0
		r = n
		ans = 0
		while l <= r:
			mid = l + (r - l) // 2
			if arr[n - mid] >= mid:
				ans = max(ans, mid)
				l = mid + 1
			else:
				r = mid - 1
		return ans