## Friday, June 24, 2016

### 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