Majority Element - II Problem Statement

Given an array/list ARR of integers with length 'N', identify all elements that appear more than floor(N/3) times within the array/list.

Input:

T (number of test cases) For each test case: - N (number of elements in the array) - A sequence of N space-separated integers representing the array elements

Output:

For each test case, output the majority elements, each separated by a space. Output the result for each test case on a new line. The order of majority elements does not need to be maintained.

Example:

Input:

2 7 3 2 3 1 4 3 3 6 1 1 2 2 3 3

Output:

3 1 2 3

Constraints:

1

Question

Majority Element - II Problem Statement

Given an array/list ARR of integers with length 'N', identify all elements that appear more than floor(N/3) times within the array/list.

Input:

T (number of test cases)
For each test case:
- N (number of elements in the array)
- A sequence of N space-separated integers representing the array elements

Output:

For each test case, output the majority elements, each separated by a space. Output the result for each test case on a new line. The order of majority elements does not need to be maintained.

Example:

Input:

2
7
3 2 3 1 4 3 3
6
1 1 2 2 3 3

Output:

3
1 2 3

Constraints:

1 <= T <= 100
3 <= N <= 5000
1 <= ARR[i] <= 10^5

Time Limit: 1 sec

Note:

You don’t need to print anything; it's already handled. Implement the given function to solve the problem.

Accepted Answer

Identify elements in an array that appear more than floor(N/3) times using efficient counting methods.

Use a HashMap to count occurrences of each element in the array.
Calculate the threshold as floor(N/3) to determine majority elements.
Iterate through the HashMap to collect elements that exceed the threshold.
Example: For array [3, 2, 3], floor(3/3) = 1, so 3 is a majority element.
Example: For array [1, 1, 2, 2, 3, 3], floor(6/3) = 2, so 1, 2, and 3 are majority elements.

Majority Element - II Problem Statement

Input:

Output:

Example:

Input:

Output:

Constraints:

Note:

Google Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern