Find a Majority with Constant Memory
National Olympiad — National round (2018 season)
Submission name: major.cpp
Problem summary
Find the value occurring more than floor(n/2) times in a sequence. Such a strict majority is guaranteed to exist.
Input
n and n positive sequence elements.
Output
The majority value.
Constraints
2 ≤ n ≤ 1000000; values ≤ 100000000; original memory limit 2 MB.
Worked example
Input and output for the worked example discussed below.
Input
9 1 3 2 3 3 4 3 3 4
Output
3
Solution analysis
- Cancel different values in pairs: a strict majority cannot disappear completely, because there are fewer non-majority elements available to cancel it. Boyer–Moore stores one candidate and a balance for the uncancelled remainder.
- When balance is zero, adopt the incoming value as the new candidate. Increase balance for a matching value and decrease it for a different one. No input array is needed.
- In the sample, the candidate may temporarily change, but the five copies of 3 outnumber the four other values. The final uncancelled candidate is 3. A verification pass would be required without the task’s majority guarantee.
Why it works
Deleting a pair of unequal values preserves the identity of any strict majority, and the balance procedure performs exactly these cancellations.
Complexity: O(n) time and O(1) auxiliary space, meeting the small memory limit without retaining input.
Watch out. The guarantee matters: a candidate is not proof that a majority exists in arbitrary data. Do not allocate a million-element array under the 2 MB limit.
Commented C++17 solution
An independently written complete program with standard headers.
// Deleting a pair of unequal values preserves the identity of any strict majority, and the balance procedure
// performs exactly these cancellations..
#include<iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count;
cin>>count;
int candidate=0;
int balance=0;
for(int index=0;index<count;index++){
int value;
cin>>value;
if(balance==0){
candidate=value;
}
balance+=value==candidate?1:-1;
}
cout<<candidate<<'\n';
}