Last Updated: 1 Oct, 2021

Max K Value

Moderate

Asked in company

Solve now

Problem statement

You are given an array ‘ARR’ of length ‘N’. You need to return the maximum possible value ‘K’ such that the total number of elements that are greater than or equal to ‘K’ is at least ‘K’.

For Example :

‘ARR’ = {3, 5, 1, 4}
In this example, the total number of elements greater than or equal to 3 are 3, 4, 5.
Hence the value of ‘K’ is 3.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the total number of elements in the array.

The next line contains ‘N’ integers denoting the elements of the array.

Output Format :

For each test case, print a single integer ‘K’ denoting the maximum possible value such that the total number of elements that are greater than or equal to ‘K’ is at least ‘K’.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 <= ‘T’ <= 10    
1 <= ‘N’ <= 5000
1 <= ‘ARR’[i] <= 10^5

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, We will iterate through all the elements and check if for the current index we have elements greater than or equal to the current index.

The steps are as follows:

Iterate through the loop from ‘N’ to 1(say iterator be i):
- Take an integer ‘count’ to store the count of elements greater than or equal to ‘i’.
- Iterate through the array ‘ARR’(say iterator be j):
  - If ‘ARR[j]’ is greater than or equal to ‘i’ increment count by 1.
- If count is greater than or equal to ‘i’:
  - Return ‘i’.

Solve now

02 Approach

In this approach, We will iterate through all the elements and store the count of all the elements in a vector and iterate through the vector till the ‘totalCount’ is greater than or equal to the current value.

The steps are as follows:

Take a vector ‘count’ of size N + 1 to store the count of all the elements.
Iterate through the array from 0 to N - 1(say iterator be i):
- If the current element is greater than n:
  - Increment the value of ‘count[n]’ by 1
- Else if the current element is less than n:
  - Increment the value of the current element in the count.
Take an integer ‘answer’ to store the number of elements greater than the current index.
Now Iterate through the ‘count’ vector from n to 1(say iterator be i):
- Update the value of ‘answer’ by ‘count[i]’.
- If ‘answer’ is greater than or equal to i:
  - Return i.

Solve now