Last Updated: 15 Nov, 2021
Max Frequency
Easy
Asked in companies
Let’s define the beauty of an array to be equal to the value present in the array, which is having the maximum frequency. If there are multiple such values, then the smallest among such values will be selected.
Alice gave Bob an array ‘A’ of size ‘N’ and asked him to find the beauty of the frequencies of the values present in the array. In simple words, Bob first needs to find the frequencies of all values present in the array, then find the beauty of this frequency array.
Help Bob in finding the beauty of the frequencies of the values present in the array.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains one integer ‘N’, denoting the size of the array.
The following line contains an array ‘A’ of ‘N’ spaced integers.
Output Format:
For each test case, print one integer in a new line denoting the beauty of the frequencies of the values present in the array.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N <= 10^4
1 <= A[i] <= 10
Time Limit: 1 sec
Approaches
In this approach, indeed of running a loop from 1 to 10 to count the frequency of each integer. We will declare another array of size 11 initialised to 0 and run a loop through the array only once. Whenever we reach any element, we will increment the value of the new array whose index is equal to the element. So we the element is 2, we will increment the value at index 2 of the new array.
Now we have an array showing the frequencies of all the elements in the original array, and we need to find the beauty value of this array which can be done as mentioned in the previous approach.
Algorithm:
- Declare an array ‘Freq’ of size 11.
- Run a loop ‘i’ from 0 to ‘N’ - 1
- Increment ‘Freq[A[i]]’ by 1.
- Initialize ‘ans’ and ‘mx’ to -1.
- Run a loop ‘i’ from 1 to 10.
- If ‘Freq[i]’ is equal to 0, continue
- Initialise ‘cn’ to 0
- Run a loop ‘j’ from 1 to 10
- If ‘Freq[j]’ equals ‘Freq[i]’, increment ‘cn’ by 1.
- If ‘cn’ is equal to ‘mx’, update ‘ans’ to a minimum of ‘ans’ and ‘Freq[i].
- Else if ‘cn’ is greater than ‘mx’, update ‘mx’ to ‘cn’ and answer to ‘Freq[i]’.
- Return ‘ans’