Find the Majority Name
Autumn Tournament (2007)
Submission name: names.cpp
Problem summary
A name is guaranteed to occur more often than all other names combined. Find it while respecting the very small memory budget.
Input
N, followed by N case-sensitive names.
Output
The name occurring strictly more than N/2 times.
Constraints
1 ≤ N ≤ 1000000; each name contains 1–20 uppercase or lowercase Latin letters; source memory limit 1 MB.
Worked example
Original statement sample.
Input
11 Rich Rich Bruck Rich Eric Stephanie Rich Rich Sally Tailor Rich
Output
Rich
Solution analysis
- Maintain a candidate name and a balance. If the balance is zero, take the next name as the candidate. An equal name increases the balance; a different name decreases it. Read names one at a time instead of storing the list or a map.
- A decrement cancels one candidate occurrence with one different occurrence. Such a pair contains at most one occurrence of the strict majority, so removing pairs cannot eliminate that majority from the residual sequence.
- In the sample, Rich appears six times out of eleven. The five other names can cancel at most five Rich occurrences; the survivor is Rich. Ordinarily a second pass would verify a candidate, but this problem explicitly guarantees a strict majority.
Why it works
Removing two unequal names preserves the identity of any strict majority: its count and the total decrease by at most one and exactly two respectively. The candidate/balance algorithm implements these cancellations. Since a strict majority exists, its name must be the final surviving candidate.
Watch out. Names are case-sensitive. The existence guarantee is essential; without it a final candidate may not be a majority. A frequency map may exceed the stated memory budget.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count;
cin>>count;
string candidate;
string name;
int balance=0;
for(int i=0;i<count;i++){
cin>>name;
if(balance==0){
candidate=name;
}
// Cancel occurrences of two different names.
balance+=name==candidate?1:-1;
}
cout<<candidate<<'\n';
}