Finding majority element in an array with hidden elements

Question

I am having trouble solving this common question with a slight twist:

Given n boxes each with a single hidden number inside, and a test procedure that decides if two boxes contain the same or different numbers, determine if there is a number which is present in the majority of the boxes, i.e. whether there are more than n/2 boxes with the same hidden number in O(n log n) time.

I am aware of Moore's Voting Algorithm but this problem seems slightly different.

Answer 1

You can use Moore's voting algorithm as is (done in O(n) time and O(1) space).

Taken from Moore's own website:

We will sweep down the sequence from the starting position.

As we sweep we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.

When we move the pointer forward over an element e:

• If the counter is 0, we set the current candidate to e and we set the counter to 1.
• If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.

When we are done, the current candidate is the majority element, if there is a majority.

Later in that example:

In some situations you know, or assume, there is a majority element.

But if you must confirm that the chosen element is indeed the majority element, you must take one more linear pass through the data to do it.

Since this algorithm only involves checking whether the current candidate matches e, just having a equality check is sufficient.

To check whether the final candidate is the majority element, just do another pass through, comparing each element to the candidate and counting the number of matches. If the number of matches is greater than n / 2, you have indeed found the majority element.