Last Updated: 3 Mar, 2021
MaxFreq_Element
Moderate
Asked in company
You are given an array/list 'ARR' of size ‘N’. It contains elements from 0 to 'K - 1' such that 'K' <= 'N'.In this array, we have to find a number that appears maximum no of times. If there is more than one such number, return the maximum one.
Follow Up:
Try to do it O(N) time complexity and O(1) space complexity.
Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.
The first line of each test case contains two integers ‘N’ and ‘K’, where ‘N' is the size of the array.
The second line contains ‘N’ single space-separated integers representing the elements of the array.
Output Format
For each test case, return the maximum occurring integer in an array.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints
1 <= 'T’ <= 50
1 <= 'N’ <= 10000
1 <= 'K' <= n
0 <= ARR[i] <= K-1 ∀ i(1,N)
Time Limit: 1sec
Approaches
Approach:-The key idea is to count the frequencies of all elements of the array. For every, ‘i’ from 1 to ‘N’ count the number of times the element A[i] is appearing from ‘i’ to ‘N’.
Algorithm:
- Create two-variable 'MAX_NO' and 'MAX_FREQ' both initialize to 0.
- For every ‘i’, 0 to ‘N-1’ count the number of times A[i] is appearing from ‘i’ to ‘N-1’.
- If the count of A[i] is greater than 'MAX_FREQ' then update the 'MAX_FREQ' to count of A[i] and 'MAX_NO' to A[i]
- If the count of A[i] is equal to 'MAX_FREQ' then 'MAX_NO' will be updated to A[i] if A[i] is greater than A[i].
Approach:-The key idea is to store the frequencies of all the elements in a map.
Algorithm:
- Run a loop from 0 to N-1 and store the frequency of A[i] in a map.
- Create two-variable ‘MAX_FREQ’ and ‘MAX_ELE’ initialize to 0.
- Run a loop from 0 to K-1 and if the frequency of ‘i’ is greater than equal to ‘MAX_FREQ’ then update 'MAX_ELE' to ‘i’ and MAX_FREQ' to the frequency of ‘i’.
- Return 'MAX_ELE'.
Approach:-The key idea is to store the frequency of A[i] at a[A[i]].To store the frequency of A[i] just do a[A[i]]+=K
Algorithm:
- For every ‘i’ from 0 to N-1 store the frequency of A[i] at A[A[i]] by doing a[A[i]%k]+=K. (A[i] is of from B+KX .The original number is ‘B’.So to get the original number simply do A[i]%K
- Now to get the 'MAX_NO' number we need to check which index is changed by the maximum amount.
- For every ‘i’ from 0 to ‘K-1’ to get the frequency of ‘i’ we can simply do A[i]/k (A[i]=b+k*x.b is the original number since b is in between 0 to ‘K-1’ . Whereas ‘X’ is the number of times we updated A[i].) If this value is greater than equal to MAX_FREQ’ then update 'MAX_NO' to ‘i'.