11

# Majority Element - II

Difficulty: EASY
Contributed By
Dhruv Sharma
Avg. time to solve
10 min
Success Rate
90%

Problem Statement

#### You are given an array/list 'ARR' of integers of length ‘N’. You are supposed to find all the elements that occur strictly more than floor(N/3) times in the given array/list.

##### Input Format :
``````The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow.

The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array.

The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.
``````
##### Output Format :
``````For each test case, return all the majority elements separated by a single space.

The output of every test case will be printed in a separate line.

You may return the majority of elements in any order.
``````
##### Note :
``````You don’t need to print anything; It has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 100
3 <= N <= 5000
1 <= ARR[i] <= 10^5

Time Limit: 1 sec
``````
##### Sample Input 1 :
``````2
7
3 2 2 1 5 2 3
5
7 4 4 9 7
``````
##### Sample Output 1:
``````2
4 7
``````
##### Explanation of Sample Input 1:
``````In the first test case, floor(N/3) = floor(7/3) is equal to 2, and 2 occurs 3 times which is strictly more than N/3. No other element occurs more than 2 times.

In the second test case, floor(N/3) = floor(5/3) is equal to 1, and 4 and 7 both occur 2 times. No other element occurs more than once.
``````
##### Sample Input 2:
``````2
6
1 2 4 4 3 4
4
6 6 6 7
``````
##### Sample Output 2:
``````4
6
``````
##### Explanation of Sample Input 2:
``````In the first test case, floor(N/3) = floor(6/3) is equal to 2, and 4 occurs 3 times which is strictly more than N/3. No other element occurs more than 2 times.

In the second test case, floor(N/3) = floor(4/3) is equal to 1, and 6 occurs 3 times. No other element occurs more than once.
``````
Console