Find all array elements occurring more than ⌊N/3⌋ times

Given an array arr[] consisting of N integers, the task is to find all the array elements having frequency more than ⌊N/3⌋ in the given array.

Examples:

Input: arr[] = {5, 3, 5}

Output: 5

Explanation:

The frequency of 5 is 2, which is more than N/3( = 3/3 = 1).

Input: arr[] = {7, 7, 7, 3, 4, 4, 4, 5}

Output: 4 7

Explanation:

The frequency of 7 and 4 in the array is 3, which is more than N/3( = 8/3 = 2).

Approach: To solve the problem, the idea is to use Divide and Conquer technique. Follow the steps below to solve the problem:

Initialize a function majorityElement() that will return the count of majority element in the array from any index left to right.

Divide the given array arr[] into two halves and repeatedly pass it to the function majorityElement().

Initialize low and high as 0 and (N – 1) respectively.

Compute the majority element using the following steps:

If low = high: Return arr[low] as the majority element.

Find the middle index,say mid(= (low + high)/2).

Recursively call for both the left and right subarrays as majorityElement(arr, low, mid) and majorityElement(arr, mid + 1, high).

After completing the above steps, merge both the subarrays and return the majority element.

Whenever the required majority element is found, append it to the resultant list.

Print all the majority elements stored in the list.

Below is the implementation of the above approach:

# Python program for the above approach 

  

class Solution: 

  

    # Function to find all elements that 

    # occurs >= N/3 times in the array 

    def majorityElement(self, a): 

  

        # If array is empty return 

        # empty list 

        if not a: 

            return [] 

  

        # Function to find the majority 

        # element by Divide and Conquer 

        def divideAndConquer(lo, hi): 

            if lo == hi: 

                return [a[lo]] 

              

            # Find mid 

            mid = lo + (hi - lo)//2

  

            # Call to the left half 

            left = divideAndConquer(lo, mid) 

  

            # Call to the right half 

            right = divideAndConquer(mid + 1, hi) 

              

            # Stores the result 

            result = [] 

            for numbers in left: 

                if numbers not in right: 

                    result.append(numbers) 

  

            result.extend(right) 

  

            # Stores all majority elements 

            ans = [] 

  

            for number in result: 

                count = 0

                  

                # Count of elements that 

                # occurs most 

                for index in range(lo, hi + 1): 

                    if a[index] == number: 

                        count += 1

                          

                # If the number is a 

                # majority element 

                if count > (hi - lo + 1)//3: 

                    ans.append(number) 

              

            # Return the list of element 

            return ans 

          

        # Function Call 

        print(divideAndConquer(0, len(a) - 1)) 

  

  

# Driver Code 

if __name__ == "__main__": 

  

    # Given array a[] 

    a = [7, 7, 7, 3, 4, 4, 4, 6] 

    object = Solution() 

  

    # Function Call 

    object.majorityElement(a) 

Output:

[7, 4]

Time Complexity: O(N*log N)

Auxiliary Space: O(log N)