Max Frequency

Easy
0/40
Average time to solve is 10m
profile
Contributed by
1 upvote
Asked in companies
Chegg Inc.DunzoIntuit

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5
1 2 1 2 3
3
7 5 5
Sample Output 1:
2
1
Explanation for Sample Input 1:
In the first test case, the frequency of 1, 2 and 3 is 2, 2 and 1, respectively. So the frequency array becomes [2, 2, 1]. Beauty of this array is 2 as it has the highest frequency.

In the second test case, the frequency of 7 and 5 is 1 and 2, respectively. So the frequency array becomes [1, 2]. In this array both elements have the same frequency, so we select the smaller one, i.e. 1.
Sample Input 2:
2
4
7 6 8 5
5
3 7 7 2 3
Sample Output 2:
1 
2
Hint

Can you create the frequency array without having to count the number of occurrences of each element individually?

Approaches (1)
Hashing

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’
Time Complexity

O(N), where ‘N’ is the length of the given array.


 

We will be iterating through the array only once, so time complexity becomes O(N).


 

Space Complexity

O(1)

We are using constant extra space.


 

Code Solution
(100% EXP penalty)
Max Frequency
Full screen
Console