# Majority Element– Boyer–Moore majority vote algorithm

Objec­tive:  Given an array of inte­ger write an algo­rithm to find the major­ity ele­ment in it (if exist).

Major­ity Ele­ment: If an ele­ment appears more than n/2 times in array where n is the size of the array.

Exam­ple:

```int [] arrA = {1,3,5,5,5,5,4,1,5};
Output: Element appearing more than n/2 times: 5

int []arrA = {1,2,3,4};
Output: No element appearing more than n/2 time
```

Ear­lier we have seen Major­ity Ele­ment solu­tions using hash map and sort­ing. In this arti­cle we will see O(n) solu­tion with con­stant extra space.

Approach: Boyer–Moore major­ity vote algorithm

In its sim­plest form, the algo­rithm finds a major­ity ele­ment, if there is one: that is, an ele­ment that occurs repeat­edly for more than half of the ele­ments of the input. How­ever, if there is no major­ity, the algo­rithm will not detect that fact, and will still out­put one of the ele­ments. A ver­sion of the algo­rithm that makes a sec­ond pass through the data can be used to ver­ify that the ele­ment found in the first pass really is a major­ity. Sourcewiki

As per above algo­rithm we can divide out imple­men­ta­tion into two parts

1. First iter­a­tion — Find the ele­ment which could be a major­ity element.
2. Sec­ond iter­a­tion – check the element(found in first iter­a­tion) count is greater than n/2

First iter­a­tion — Find the ele­ment which could be a major­ity element

• Say Array has 10 ele­ments and say ele­ment x appears 6 times. Rest of the ele­ments count = 4. If we start can­cel out each occur­rence of x with rest of the ele­ments, still at the end we will have some count of x remain­ing. In our exam­ple (6–4 =2, x count )
• Iter­ate through array and main­tain the count of majority_element.(starts with first ele­ment in the array.)
• If next ele­ment is same then incre­ment the count
• If next ele­ment is not same then decre­ment the count.
• If count becomes zero then majority_element = cur­rent ele­ment, count =1.
• After the first iter­a­tion majority_element will be the can­di­date which might have the count > n/2.

Sec­ond iter­a­tion – check the ele­ment (found in first iter­a­tion) count is greater than n/2

• Iter­ate through array and get the count of ele­ment found in first step. If count is >n/2 then print it.
• If count is less than n/2 then ignore it, array does not have major­ity element.

Time Com­plex­ity: O(n), Space Com­plex­ity: O(1)

Exam­ple:

```First Iteration:

int [] arrA = {5,3,3,5,5,1,5};
i = 0, majority_element = 5
count  = 1

int [] arrA = {5,3,3,5,5,1,5};
i = 1, current_element=3, majority_element = 5
count=0 (current element is not same, count = count -1)

int [] arrA = {5,3,3,5,5,1,5};
i = 2, current_element=3, majority_element = 3
count=1 (count was 0 so, majority_element = current_element)

int [] arrA = {5,3,3,5,5,1,5};
i = 3, current_element=5, majority_element= 3
count=0(current element is not same, count = count-1)

int [] arrA = {5,3,3,5,5,1,5};
i = 4 current_element=5, majority_element= 5
count = 1(count was 0 so, majority_element = current_element)

int [] arrA = {5,3,3,5,5,1,5};
i = 5, current_element=1, majority_element= 5,
count=0(current element is not same, count = count-1)

int [] arrA = {5,3,3,5,5,1,5};
i = 6, current_element=5, majority_element= 5
count = 1(count was 0 so, majority_element = current_element)

Now majority_element = 5,

Do the second iteration and check the count of 5.
```

Code:

Out­put:

` Element appearing more than n/2 times: 5`