This algorithm tries to find out the majority number in two iterations. In the first iteration, a probable candidate for majority number is found. In second iteration, we check if the candidate is really the majority number by counting it’s frequency.
The first iteration works as follows. We initialize the first element as the majority number and the count variable is initialized with 1. During further iterations, if the element is equal to majority number, we increment the count, otherwise we decrement the count. If at any point, the count reaches zero, We reassign the majority number to the current element and assign 1 to count.
For example, let us consider the input array {6, 2, 3, 6, 3, 6, 6, 6}. The following table explains the logic.
| Iteration# | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Data | 6 | 2 | 6 | 6 | 3 | 6 | 1 | 6 |
| Majority | 6 | 2 | 6 | 6 | 6 | 6 | 6 | 6 |
| count | 1 | 1 | 1 | 2 | 1 | 2 | 1 | 2 |
At the end 6 is the candidate for majority number. In the second iteration we check the frequency of 6. If it is more than half of the array size it is the majority element.
Here is the Java implementation of this approach.