Finding the majority number from given array : Moore's majority Voting algorithm

Majority number in a given sequence of numbers is a number that occurs more than N/2 times where N is the count of numbers in the sequence. We can find the majority number in multiple ways.

1. Brute force method: Have two nested loops which will calculate of maximum count of each elements then compare which element appears maximum time in array from stored count, then check if its count exceeds N/2. Time complexity : O(N*N)
2. Using Hash Map as temporary storage: Traverse array once, while traversing through array keep count of each element in the hash map with element from array as key and its count as value. Then traverse through map to find out which is maximum occurring element. Time complexity : O(NlogN) and space complexity O(N)
3. Using Moore’s Voting Algorithm:  First iterate through array to find out if array contains the majority number. In second iteration confirm if its majority number. Below is the code for finding majority number using Moore's voting algorithm.

//Code to find out majority number present in the given array using Moore's Voting algorithm   #include <iostream> using namespace std; void MajorityNumber( int * input, int size ) {     if( size <= 0 )     {         cout << "NONE" << endl;         return;     }     if ( NULL == input )     {         cout << "NONE" << endl;         return;     }     if( size == 1 )     {         cout << "Majority Number : " << input[0] << endl;         return;     }     int nCurrent = input[0];     int nCounter = 1;     for( int nIterator = 1; nIterator < size; nIterator++ )     {         if( input[nIterator] == nCurrent )         {             nCounter++;         }         else         {             nCounter--;             if(nCounter == 0 )             {                 nCounter = 1;                 nCurrent = input[nIterator];             }         }     }     if( nCounter <= 0)     {         cout << "NONE" << endl;         return;     }     nCounter = 0;     for( int i = 0; i < size; i++)     {         if( input[i] == nCurrent )         {             nCounter++;         }     }     if( nCounter > (size/2) )     {         cout << "Majority Number: " << nCurrent << endl;         return;     }     cout << "NONE" << endl; } int _tmain(int argc, _TCHAR* argv[]) {     int arrays[4][9] = {                         {9, 8, 8, 9, 3, 8, 6, 8, 8 },                         {17,17,11,17, 11, 11, 11, 17, 17},                         {11,11,8,8, 8, 11, 11, 11,8},                         {10,10,10, 11, 11, 11, 11, 11, 10}                      };        for( int i =0; i < 4; i++)     {         MajorityNumber( arrays[i], 9 );     }     return 0; }

Above method loops through each element and maintains a count of current element, If the next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the current element to the next element and sets count to 1. Out put of above code will be as below.

NONE Majority Element : 17 Majority Element : 11 Majority Element : 11