Concept used to solve the above problem is, if an array contains a majority element then at least one of the halves will contain a majority element.
STEP 1:- Start
STEP 2:- Recursively divide the arrays into 2 halves until there are only one or two elements in the array.
STEP 3:- If there is only one element return that element to the upper level.
STEP 4:- If there are two elements then if they are equal then return that element otherwise return -1 to the upper level.
STEP 5:- If both the values returned by the lower level are -1 then return -1 to the upper level.
STEP 6:- Otherwise check the value (not -1) returned by the lower level array to the upper level array is a majority element in the upper level array or not.
STEP 7:- If it is majority then return the value to the upper level otherwise return -1 to the upper level.
STEP 8:- Repeat steps 5 to 7 untill we reach the original array.
STEP 9:- If (-1) is returned by the original array then print there is no majority element in the array . Otherwise print the returned value as the majority element.
STEP 10:- STOP.
EXAMPLE
• Consider A,B and C as JPEG images.
• All the values returned from the lower level array to higher level are written in red.
Explanation of Time Complexity
Height of recurrence tree = O(log n).
Checking whether the returned element is majority or not takes O(n) time.
Hence time complexity = O(n logn).