Largest Number X Which Occurs X Times

Easy

0/40

Contributed by

6 upvotes

Asked in company

Problem statement

Given an array ‘A’ consisting of ‘N’ integers, you should return the biggest value ‘X’, which occurs in ‘A’ exactly ‘X’ times. If there is no such value, you should return 0.

For example:

In the given array A[] = {1, 2, 2, 3, 3, 3,}  1 has occurred 1 times, 2 has occurred 2 times and 3 has occurred 3 times. So we will return 3 since it is the maximum number.

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 an integer ‘N’, denoting the number of integers.
The second line of each test case contains ‘N’ space-separated integers.

Output Format :

For each test case, print the highest number ‘X’ which has appeared ‘X’ a number of times.

 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 <= N <= 10^5
1<= array[i] <= 10^9

Time limit: 1 sec

Sample Input 1 :

2
6
3 8 2 3 3 2
5
4 3 2 1 2

Sample Output 1 :

3
2

Explanation For Sample Output 1 :

For test case 1 :
Number ‘3’ has appeared ‘3’ times, so we will return 3.

For test case 2 :
Number ‘2’ has appeared ‘2’ times, so we will return 2.

Sample Input 2 :

2
6
1 2 3 5 3 3
6
1 1 2 2 1 1

Sample Output 2 :

3
2

Hint 1

Hint 2

Try to Sort the elements and then count the frequency of numbers from highest number to lowest number

Approaches (2)

Approach 1

Approach 2

Sortings

Lets first Sort the array in descending order

Then we can perform the following steps:

Traverse from start, we know that the maximum element will be in the start.
Count its frequency, and check whether it is equal to the value of the element.
If yes, then
- Simply return this number
Otherwise,
- Keep traversing until we find such an element.

We can also sort the array in ascending order and do the reverse of what is described in the above steps.

Time Complexity

O( N * log( N ) ), where ‘N’ is the size of the array

Since we are initially sorting the array, it will take O(N * log( N )) complexity.

Space Complexity

O( 1 )

As we have not used any extra space.

(100% EXP penalty)

Largest Number X Which Occurs X Times

Console