Moore's Voting Algorithm is an algorithm used to find the element that appears more than half the time in an array.

## Finding the Majority Element

Moore's Voting Algorithm is an algorithm used to find the element that appears more than half the time in an array. The basic idea of the algorithm is to find the element with a count exceeding half through the cancellation of different elements.

The algorithm steps are as follows:

- Initialize two variables
`candidate`

and`count`

, representing the candidate element and the counter. Initially, set`candidate`

to the first element of the array and`count`

to 1. - Traverse the array, starting from the second element:
- If the current element is the same as
`candidate`

, increment the`count`

by 1. - If the current element is different from
`candidate`

, decrement the`count`

by 1.- If
`count`

becomes 0, set the current element as the new`candidate`

and reset`count`

to 1.

- If

- If the current element is the same as
- The final
`candidate`

is the element that may appear more than half the time. - Traverse the array, count the occurrences of the
`candidate`

, and ensure its count indeed exceeds half.

Below is an example code demonstrating how to use Moore's Voting Algorithm to find the element that appears more than half the time:

In the above example, for the array `{2, 4, 2, 2, 5, 2, 2, 6, 2, 2, 8}`

, the element `2`

appears more than half the time, so the algorithm outputs `2`

.

## Extension: Finding Elements Appearing more than n-th of the Total

Moore's Voting Algorithm can be modified to find elements that appear more than n-th of the total count. The key modification lies in determining the required counting threshold.

Assuming the array length is `size`

, to find elements that appear more than n-th of the total count, set the counting threshold to `size / n`

. This means that when the count of an element reaches this threshold, it can be considered a valid element.

When finding elements that appear more than n-th of the total count, the following modifications can be made to Moore's Voting Algorithm:

- Initialize two arrays
`candidate`

and`count`

, both with a length of n-1. The`candidate`

array is used to store candidate elements, and the`count`

array is used to store corresponding counters. Initially, set all elements of the`candidate`

array to -1 and all elements of the`count`

array to 0. - Traverse the array for each element:
- Check if the same candidate element exists in the
`candidate`

array for the current element.- If found, increment the corresponding counter by 1.
- If not found, find the first position in the
`candidate`

array where the counter is 0. Set the current element as a new candidate in that position and set the corresponding counter to 1.- If no position with a counter of 0 is found, it means the
`candidate`

array is full. In this case, decrement all counters by 1 to cancel out one element.

- If no position with a counter of 0 is found, it means the

- Check if the same candidate element exists in the
- Traverse the
`candidate`

array and validate whether each candidate element appears more than`size / n`

times. Count the occurrences of each candidate in the original array, and if it exceeds`size / n`

, output that candidate. - If no candidate element appears more than n-th of the total count, there is no element satisfying the condition.

The modified algorithm steps above involve traversing the array, using candidate elements and counters to cancel out, and ultimately finding elements that appear more than n-th of the total count.

Below is the modified example code:

In the above example, for the array `{2, 4, 2, 2, 5, 2, 2, 6, 2, 2, 8, 3, 3, 3, 3}`

, both elements `2`

and `3`

appear more than 4-th of the total count, so the algorithm outputs: