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.
Examples :
Input: [2, 3, 4, 5, 6, 7]
Output: 4
Explanation : 4 elements [4, 5, 6, 7]
are greater than equal to 4
Input: [1, 2, 3, 4]
Output: 2
Explanation : 3 elements [2, 3, 4] are
greater than equal to 2
Input: [4, 7, 2, 3, 8]
Output: 3
Explanation : 4 elements [4, 7, 3, 8]
are greater than equal to 3
Input: [6, 7, 9, 8, 10]
Output: 5
Explanation : All 5 elements are greater
than equal to 5
Expected time complexity : O(n)
Method 1 [Simple : O(n2) time] :
Let size of input array be n. Let us consider following important observations.
- The maximum possible value of result can be n. We get the maximum possible value when all elements are greater than or equal to n. For example, if input array is {10, 20, 30}, n is 3. The value of result can’t be greater than 3.
- The minimum possible value would be 1. An example case when get this output is, when all elements are 1.
So we can run a loop from n to 1 and count greater elements for every value.
C++
// C++ program to find maximum possible value K// such that array has at-least K elements that// are greater than or equals to K.#include <iostream>using namespace std;// Function to return maximum possible value K// such that array has atleast K elements that// are greater than or equals to Kint 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;}// Driver codeint main(){ unsigned int arr[] = {1, 2, 3, 8, 10 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findMaximumNum(arr, n); return 0;} |
Java
// Java program to find maximum// possible value K such that // array has at-least K elements // that are greater than or equals to K.import java.io.*;class GFG {// Function to return maximum // possible value K such that // array has atleast K elements // that are greater than or equals to Kstatic int findMaximumNum(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;}// Driver codepublic static void main (String[] args) {int arr[] = {1, 2, 3, 8, 10 };int n = arr.length; System.out.println(findMaximumNum(arr, n));}}// This code is contributed by aj_36 |
Python3
# python 3 program to find maximum possible value K# such that array has at-least K elements that# are greater than or equals to K.# Function to return maximum possible value K# such that array has atleast K elements that# are greater than or equals to Kdef findMaximumNum(arr, 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 i = n while(i >= 1): # count contains total number of elements # in input array that are more than equal to i count = 0 # traverse the input array and find count for j in range(0,n,1): if (i <= arr[j]): count += 1 if (count >= i): return i i -= 1 return 1# Driver codeif __name__ == '__main__': arr = [1, 2, 3, 8, 10] n = len(arr) print(findMaximumNum(arr, n))# This code is contributed by# Surendra_Gangwar |
C#
// C# program to find maximum// possible value K such that // array has at-least K elements // that are greater than or equals to K.using System;class GFG{ // Function to return maximum // possible value K such that // array has atleast K elements // that are greater than or equals to Kstatic int findMaximumNum(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;}// Driver codestatic public void Main (){ int []arr = {1, 2, 3, 8, 10 }; int n = arr.Length; Console.WriteLine(findMaximumNum(arr, n));}}// This code is contributed by m_kit |
PHP
<?php// PHP program to find maximum // possible value K such that // array has at-least K elements // that are greater than or // equals to K.// Function to return maximum // possible value K such that// array has atleast K elements // that are greater than or // equals to Kfunction findMaximumNum($arr, $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 ($i = $n; $i >= 1; $i--) { // count contains total // number of elements in // input array that are // more than equal to i $count = 0; // traverse the input // array and find count for ($j = 0; $j < $n; $j++) if ($i <= $arr[$j]) $count++; if ($count >= $i) return $i; } return 1;}// Driver code$arr = array (1, 2, 3, 8, 10);$n = sizeof($arr);echo findMaximumNum($arr, $n);// This code is contributed by ajit?> |
Javascript
<script> // Javascript program to find maximum // possible value K such that // array has at-least K elements // that are greater than or equals to K. // Function to return maximum // possible value K such that // array has atleast K elements // that are greater than or equals to K function findMaximumNum(arr, 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 (let i = n; i >= 1; i--) { // count contains total // number of elements // in input array that // are more than equal to i let count = 0; // traverse the input // array and find count for (let j = 0; j < n; j++) if (i <= arr[j]) count++; if (count >= i) return i; } return 1; } let arr = [1, 2, 3, 8, 10 ]; let n = arr.length; document.write(findMaximumNum(arr, n)); </script> |
Output
3
Time Complexity : O(N2) ,here N is size of array.
Space Complexity : O(1) ,since no extra space required.
Method 2 [Efficient : O(n) time and O(n) extra space]
- The idea is to construct auxiliary 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.
- We process all input elements.
- If an element arr[i] is less than n, then we increment its frequency, i.e., we do freq[arr[i]]++.
- Else we increment freq[n].
- After step 2 we have two things.
- Frequencies of elements for elements smaller than n stored in freq[0..n-1].
- 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.
Below is implementation of above idea.
C++
// C++ program to find maximum possible value K such// that array has atleast K elements that are greater// than or equals to K.#include <bits/stdc++.h>using namespace std;// Function to return maximum possible value K such// that array has at-least K elements that are greater// than or equals to K.int findMaximumNum(unsigned int arr[], int n){ // construct auxiliary 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 auxiliary 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 auxiliary 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; }}// Driver codeint main(){ unsigned int arr[] = {1, 2, 3, 8, 10 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findMaximumNum(arr, n); return 0;} |
Java
// Java program to find maximum possible value K such// that array has atleast K elements that are greater// than or equals to K.import java.util.Vector;class GFG {// Function to return maximum possible value K such// that array has at-least K elements that are greater// than or equals to K. static int findMaximumNum(int arr[], int n) { // construct auxiliary array of size n + 1 and // initialize the array with 0 int[] freq=new int[n+1]; for (int i = 0; i < n + 1; i++) { freq[i] = 0; } // store the frequency of elements of // input array in the auxiliary 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 auxiliary 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; } } return 0; }// Driver code public static void main(String[] args) { int arr[] = {1, 2, 3, 8, 10}; int n = arr.length; System.out.println(findMaximumNum(arr, n)); }}/*This Java code is contributed by koulick_sadhu*/ |
Python3
# Python program to find maximum possible value K such# that array has atleast K elements that are greater# than or equals to K.# Function to return maximum possible value K such# that array has at-least K elements that are greater# than or equals to K.def findMaximumNum(arr, n): # construct auxiliary array of size n + 1 and # initialize the array with 0 freq = [0 for i in range(n+1)] # store the frequency of elements of # input array in the auxiliary array for i in range(n): # If element is smaller than n, update its # frequency if (arr[i] < n): freq[arr[i]] += 1 # Else increment count of elements greater # than n. else: freq[n] += 1 # sum stores number of elements in input array # that are greater than or equal to current # index sum = 0 # scan auxiliary array backwards for i in range(n,0,-1): sum += freq[i] # if sum is greater than current index, # current index is the answer if (sum >= i): return i# Driver codearr = [1, 2, 3, 8, 10]n = len(arr)print(findMaximumNum(arr, n))# This code is contributed by shinjanpatra |
C#
// C# program to find maximum possible value K such // that array has atleast K elements that are greater // than or equals to K.using System;using System.Collections.Generic;class GFG{ // Function to return maximum possible value K such // that array has at-least K elements that are greater // than or equals to K. static int findMaximumNum(int []arr, int n) { // construct auxiliary array of size n + 1 and // initialize the array with 0 List<int> freq = new List<int>(); for (int i = 0; i < n + 1; i++) { freq.Insert(i, 0); } // store the frequency of elements of // input array in the auxiliary array for (int i = 0; i < n; i++) { // If element is smaller than n, update its // frequency if (arr[i] < n) //freq[arr[i]]++; { freq.Insert(arr[i], freq[arr[i]] + 1); } // Else increment count of elements greater // than n. else { freq.Insert(n, freq[n] + 1); } //freq[n]++; } // sum stores number of elements in input array // that are greater than or equal to current // index int sum = 0; // scan auxiliary 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; } } return 0; } // Driver code public static void Main() { int []arr = {1, 2, 3, 8, 10}; int n = arr.Length; Console.WriteLine(findMaximumNum(arr, n)); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// Javascript program to find maximum possible value K such// that array has atleast K elements that are greater// than or equals to K.// Function to return maximum possible value K such// that array has at-least K elements that are greater// than or equals to K.function findMaximumNum(arr, n){ // construct auxiliary array of size n + 1 and // initialize the array with 0 let freq = new Array(n + 1).fill(0); // store the frequency of elements of // input array in the auxiliary array for (let 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 let sum = 0; // scan auxiliary array backwards for (let 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; }}// Driver codelet arr = [1, 2, 3, 8, 10];let n = arr.length;document.write(findMaximumNum(arr, n));// This code is contributed by gfgking.</script> |
Output
3
This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
