Problem
Find the majority number in a given sequence of numbers
(a number that occurs more than N/2 times where N is the count of numbers in the sequence).
Don't maintain a map of all occurring numbers along with a count.
No number may be a majority.
Example: 1 1 2 3 4 1 6 1 7 1 1
Majority number is 1 since it occurs 6 times (> 11/2)
Solution
If there is a majority number, at least 2 in 3 consecutive numbers are same.
Find the candidates
Check candidates whether meet the requirements
If possible, early terminate the loop
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the majority number in a given sequence of numbers
Created Date : 16-06-2013
Last Modified : 17-06-2013
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <iterator>
#include <algorithm>
using namespace std;
bool FindMajorityNumber(int* arr, int len, int& majorNum)
{
int* candidate = new int[len];
int candidateLen(0);
int* pCandidate(candidate);
bool retVal(false);
for(int i = 0; i < len + 2; i += 3){
int a = arr[i];
int b = arr[(i + 1) % len];
int c = arr[(i + 2) % len];
if(a == b || a == c){
*pCandidate = a;
pCandidate ++;
}
else if(b == c){
*pCandidate = b;
pCandidate ++;
}
}
candidateLen = pCandidate - candidate;
for(int i = 0; i < candidateLen; ++i){
int cnt(0);
for(int j = 0; j < len; j++){
if(candidate[i] == arr[j]){
cnt ++;
}
if(cnt > len / 2){
majorNum = candidate[i];
retVal = true;
goto EXIT;
}
}
}
EXIT:
delete[] candidate;
return retVal;
}
int main(int argc, char* argv[])
{
int testCase[20] = {1, 1, 2, 3, 4, 1, 6, 1, 7, 1, 1};
int len = 11; //sizeof(testCase)/sizeof(testCase[0]);
int majorNum;
cout << "Test case 0" << endl;
for(int j = 0; j < len; j++){
cout << setw(4) << testCase[j];
}
cout << endl;
bool found = FindMajorityNumber(testCase, len, majorNum);
if(found){
cout << "The major number is " << majorNum << endl;
}
else{
cout << "There is no major number!" << endl;
}
cout << " --------------------------------- " << endl;
len = 20;
for(int i = 1; i < len; ++i){
cout << "Test case " << i << endl;
for(int j = 0; j < i; j++){
if(i < 9){
testCase[j] = rand() % i;
}
else{
testCase[j] = rand() % (i - i / 2 - i / 4 - i / 8);
}
cout << setw(4) << testCase[j];
}
cout << endl;
found = FindMajorityNumber(testCase, i, majorNum);
if(found){
cout << "The major number is " << majorNum << endl;
}
else{
cout << "There is no major number!" << endl;
}
cout << " --------------------------------- " << endl;
}
return 0;
}
Output
Test case 0
1 1 2 3 4 1 6 1 7 1 1
The major number is 1
---------------------------------
Test case 1
0
The major number is 0
---------------------------------
Test case 2
1 0
There is no major number!
---------------------------------
Test case 3
1 2 1
The major number is 1
---------------------------------
Test case 4
2 2 2 0
The major number is 2
---------------------------------
Test case 5
0 0 1 2 1
There is no major number!
---------------------------------
Test case 6
5 1 2 3 0 3
There is no major number!
---------------------------------
Test case 7
2 3 6 5 6 5 5
There is no major number!
---------------------------------
Test case 8
6 7 7 6 3 2 5 0
There is no major number!
---------------------------------
Test case 9
1 1 1 0 1 1 0 1 1
The major number is 1
---------------------------------
Test case 10
0 1 1 1 0 1 0 0 1 1
The major number is 1
---------------------------------
Test case 11
1 2 0 1 1 1 2 2 0 0 1
There is no major number!
---------------------------------
Test case 12
0 0 0 0 0 1 0 1 0 0 0 1
The major number is 0
---------------------------------
Test case 13
0 2 0 2 0 1 0 2 1 2 2 1 0
There is no major number!
---------------------------------
Test case 14
0 2 1 2 1 2 0 0 2 0 2 1 0 0
There is no major number!
---------------------------------
Test case 15
2 1 2 1 2 1 1 0 0 2 1 1 1 1 0
The major number is 1
---------------------------------
Test case 16
0 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0
The major number is 0
---------------------------------
Test case 17
0 2 1 0 1 2 0 0 2 2 1 2 2 0 2 1 2
There is no major number!
---------------------------------
Test case 18
1 0 2 0 2 0 2 1 2 0 2 2 0 1 0 2 2 1
There is no major number!
---------------------------------
Test case 19
0 2 0 0 1 0 3 0 0 1 2 1 3 2 2 0 0 3 3
There is no major number!
---------------------------------
Press any key to continue . . .