## Summary

No one is supposed to invent the Boyer–Moore voting algorithm during the interview. The point is how to write bug-free codes and make interviewers happy. The order of the branches are quite tricky here.

**Please remember to increase cnt first, then check if cnt==0, and finally decrease cnt. **

Several good points here to mention,

- There’s only one majority number if it exists;
- If we eliminate the same number of majority numbers and non-majority numbers, the majority number still has larger frequencies than other numbers.
- If a
`cnt`

turns into`0`

, it means we have met the same number of majority numbers and non-majority numbers.

### n/2

Given a non-empty array of size *n*, find the majority element. The majority element is the element that appears **more than** `⌊ n/2 ⌋`

times.

```
int cnt = 0;
int cand = ll{INT_MIN} - 1;
for (auto num : nums) {
if (num == cand) {
cnt++;
} else if (cnt == 0) {
cand = num;
cnt = 1;
} else {
cnt--;
}
}
```

### n/3

Given a non-empty array of size *n*, find all majority elements. The majority element is the element that appears **more than** `⌊ n/3 ⌋`

times.

The order of branches are extremely tricky here.

The correct order should avoid `cand0`

and `cand1`

get the same value, so at first we should check if the current value is in the two candidates or not.

```
ll cand0 = ll{INT_MIN} - 1, cnt0 = 0;
ll cand1 = ll{INT_MIN} - 1, cnt1 = 0;
for (auto num : nums) {
if (cand1 == num) {
cnt1++;
} else if (cand0 == num) {
cnt0++;
} else if (cnt1 == 0) {
cand1 = num;
cnt1 = 1;
} else if (cnt0 == 0) {
cand0 = num;
cnt0 = 1;
} else {
cnt0--;
cnt1--;
}
}
```

The following order will fail in case `[1,2,2,3,2,1,1,3]`

. Since at index `3`

, `cnt1`

will turn into `0`

, so at index4 `cnt1`

will be the `2`

, which causes duplication.

```
for (auto num : nums) {
if (cand1 == num) {
cnt1++;
} else if (cnt1 == 0) {
cand1 = num;
cnt1 = 1;
} else if (cand0 == num) {
cnt0++;
} else if (cnt0 == 0) {
cand0 = num;
cnt0 = 1;
} else {
cnt0--;
cnt1--;
}
}
```