edited by
1,089 views
1 votes
1 votes
You have an array $A$ with $n$ objects, some of which are identical. You can check if two objects are equal but you cannot compare them in any other way — i.e., you can check $A[i] == A[j]$ and $A[i] != A[j]$, but comparisons such as $A[i] < A[j]$ are not meaningful. (Imagine that the objects are JPEG images.) The array A is said to have a majority element if strictly more than half of its elements are equal to each other. Use divide and conquer to come up with an $O(n \log n)$ algorithm to determine if $A$ has a majority element.
edited by

1 Answer

2 votes
2 votes

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).

Related questions

12 votes
12 votes
4 answers
3
go_editor asked May 27, 2016
1,449 views
Let $A$ be an array of $n$ integers, sorted so that $A \leq A \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there exist indices $k$ a...