Malamal Weekly

Easy
0/40
Average time to solve is 20m
profile
Contributed by
5 upvotes
Asked in company
Snapdeal Ltd.

Problem statement

Nowadays, Ninja tries his luck every week in buying a lottery ticket just by selecting some random numbers. But this time he got some insider information about the lottery that how a winner is selected this time.

So the information is that the lottery chart contains the number in form of an array/list 'ARR' and for winning the lottery Ninja has to find out the largest element with minimum frequency from that chart or we can say 'ARR'.

So help our Ninja in selecting the number, so that Ninja is able to win the lottery.

Formally, find the largest number with minimum frequency from the given 'ARR'.

Example: 
You have given an array {2, 2, 5, 50, 1} so in this array ‘50’ is the largest number with minimum frequency.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then, the 'T' test cases follow. 

The first line of each test case contains a positive integer 'N' denoting the size of the array.

The second line of each test case contains an array ‘ARR[i]’ containing ‘N’ number of values.
Output Format: 
For each test case, print the largest number with minimum frequency.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10^2
1 <= N <= 10^3
1 <= ARR[i] <= 10^9

Where ‘T’ represents the number of test cases and ‘N’ represents the size of array and ‘ARR[i]’ represents the elements of array.

Time Limit: 1sec

Sample Input 1:

2
5
9 9 9 2 5
5
5 5 4 6 4

Sample Output 1:

5
6

Explanation For Sample Input 1:

In first test case, ‘5’ is the size of the array. In the second line elements of the array are given so according to this array ‘5’ and ‘2’ are the elements with minimum frequency but as ‘5 is larger than ‘2’, So, ‘5’ is the answer.

In the second test case, ‘6’ is the number with the smallest frequency.

Sample Input 2 :

2
3
1 1 1
5
50 50 1 30 30

Sample Output 2 :

1
1

Explanation For Sample Input 2:

In the first test case, ‘3’ is the size of the array and all elements are '1'. So, ‘1’ is the answer.

In the second test case, ‘1’ is the number with the smallest frequency.
Hint

Can you try to sort the elements in a different fashion?

Approaches (2)
Sorting

Algorithm is as follows: 

 

  1. In this approach, we want to map the frequency of each element so we define a structure named 'ELE' which contains three fields ‘COUNT’ to store the frequency of elements, ‘VAL’ to store the value of that element, ‘INDEX’ to store the index of that element. Initially, we initialize the ‘COUNT’ of each element as ‘0’.
  2. Now we sort our structure according to the value. We are sorting our structure so that we can easily able to count the frequency of the elements.
  3. Now for counting the frequency we initialize the ‘COUNT’ of the first element of the structure as "1" and as we traverse through the structure we check:
    • If the previous element is equal to the current element we increase the ‘COUNT’ of the current element and make the ‘COUNT’ of the previous element ‘-1’.
    • Else we again make the ‘COUNT’ of the element as ‘1’.
  4. Now we again sort the structure now on the basis of the count of the frequency.
  5. Now we fill our array if the ‘COUNT’ is not equal to ‘-1’ from the structure.
  6. The last index of the array is our answer i.e. ‘ARR[N-1]’.
Time Complexity

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

 

As we are using sorting so it takes 0(N * logN) time to sort a ‘N’ size array.

Space Complexity

O(N), where ‘N’ is the size of an array.

 

 As we are creating an another array/list of size ‘N’.

Code Solution
(100% EXP penalty)
Malamal Weekly
Full screen
Console