Malamal Weekly

Posted: 5 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
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
Approach 1

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]’.
Try Problem