Majority Element (n/3 times)

Problem Statement: Given an array of integers, find all elements that appear more than n/3 times. The algorithm should run in linear time and use constant space.

Example:

Input: arr = [3, 2, 3]

Output: [3]

Solution:

To find elements that appear more than n/3 times, we can use the Boyer-Moore Voting Algorithm.

Steps to Solve:

1.    Initialize two candidate elements and their counts.

2.    First pass:

• Find potential candidates.

3.    Second pass:

• Verify the candidates.

Time Complexity: O(n)

Space Complexity: O(1)