Finding the Majority QQ Number: Moore Voting Algorithm Explained

The author introduces a Tencent interview problem: given 2N QQ numbers, one of them appears more than N times, and the task is to find that number with the lowest possible time and space complexity.

First, a brute‑force sorting solution is described. By sorting the array, the element at the middle index must be the majority element, but the sorting step costs O(N log N) time, which is not optimal for the interview.

Next, a counting approach using a hash map is presented. It achieves O(N) time by tallying frequencies, yet it also requires O(N) extra space, which again fails the interview’s strict constraints.

The article then introduces the Moore voting algorithm, an elegant O(N) time and O(1) space method that satisfies the interview requirements. The algorithm treats the problem like a class‑president election: each vote either increments the current candidate’s count or cancels it out, guaranteeing that the majority element remains as the final candidate.

An illustrative example shows how votes are processed step by step, demonstrating how the majority candidate survives repeated cancellations.

Below is the complete C++ implementation of the Moore voting algorithm, including debug logging to trace the internal state:

#include <iostream>
using namespace std;

int solution(int a[], int n)
{
    int count = 0, value = a[0];
    for(int i = 0; i < n; i++)
    {
        printf("log, i=%d, count=%d, value=%d
", i, count, value);
        if(count == 0)
        {
            value = a[i];
        }
        if(a[i] == value)
        {
            count++;
        }
        else
        {
            count--;
        }
    }
    return value;
}

int main()
{
    int a[] = {6,2,5,3,4,2,2,2,2,5};
    int n = sizeof(a) / sizeof(a[0]);
    cout << solution(a, n) << endl;
    return 0;
}

Running the program produces the following log and final result, confirming that the number 2 is the majority element:

log, i=0, count=0, value=6
log, i=1, count=1, value=6
log, i=2, count=0, value=6
log, i=3, count=1, value=5
log, i=4, count=0, value=5
log, i=5, count=1, value=4
log, i=6, count=0, value=4
log, i=7, count=1, value=2
log, i=8, count=2, value=2
log, i=9, count=3, value=2
2

The author concludes that understanding this algorithm helps candidates solve similar majority‑element problems efficiently during interview preparation.