Problem

Submissions

Hints & solutions

Discuss

Max K Value

Moderate

0/80

Average time to solve is 10m

Contributed by

1 upvote

Asked in company

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

Sample Output 1 :

3
4

Explanation For Sample Input 1 :

In the first test case, 3 is the largest element in the array for which we have more than three elements having values greater than 3. Hence the answer is 3.

In the second test case, the elements greater than or equal to 4 are 4: { 4, 5. 6. 20}.  Hence the answer is 4.

Sample Input 2 :

Sample Output 2 :

3
2

Hint 1

Hint 2

Iterate through all the indexes from 0 to N and check if the current index has more elements greater than or equal to the current index.

Approaches (2)

Approach 1

Approach 2

Brute Force 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’.

Time Complexity

O( N ^ 2 ), where N is the size of the array.

As we are iterating from 1 to N and for every index we are checking the count of elements greater than the current index.

Hence the time complexity is O( N ^ 2 ).

Space Complexity

O( 1 )

As no extra space is used.

Hence the space complexity is O(1).

(100% EXP penalty)

Max K Value

Console