Count Element Occurences (Function Program)
Given an array of size n, find all elements in array that appear more than n/k times.
Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the array. Then the next line contains n space separated integers forming the array. The last line of input contains an integer k.
Output: Print the count of elements in array that appear more than n/k times.
Constraints: 1<=T<=10^5
1<=N<=10^5
1<=a[i]<=10^5
1<=k<=N
Example:
Input: 2
8
3 1 2 2 1 2 3 3
4
4
2 3 3 2
3
Output: 2
2
Solution:
We can solve this question using several method like : count each number and compare with n/k.
But its take o(n^2) or may be more than that.
But if we first sort the array and then check each number than its pass all test case.
So i solve this question by using c++ inbuilt sort function and than compare each number with its next number if its similar to its next number in that case increase the count by one other wise compare that count with n/k.
If count is equal or greater than given n/k so we increase the final count and in final step print the final count on stdout. Here i attached my source code ->
0 Comments