NOTE & BLOG

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:

1. 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.
2. 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.
3. The final candidate is the element that may appear more than half the time.
4. 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:

#include <stdio.h>

int findMajorityElement(int arr[], int size) {
    int candidate = arr[0];
    int count = 1;

    for (int i = 1; i < size; i++) {
        if (arr[i] == candidate) {
            count++;
        } else {
            count--;
            if (count == 0) {
                candidate = arr[i];
                count = 1;
            }
        }
    }

    // Validate whether the candidate is the element appearing more than half the time
    int freq = 0;
    for (int i = 0; i < size; i++) {
        if (arr[i] == candidate) {
            freq++;
        }
    }
    if (freq > size / 2) {
        return candidate;
    } else {
        return -1;  // No element found appearing more than half the time
    }
}

int main() {
    int arr[] = {2, 4, 2, 2, 5, 2, 2, 6, 2, 2, 8};
    int size = sizeof(arr) / sizeof(arr[0]);

    int majorityElement = findMajorityElement(arr, size);

    if (majorityElement != -1) {
        printf("The element appearing more than half the time is: %d\n", majorityElement);
    } else {
        printf("No element appearing more than half the time\n");
    }

    return 0;
}

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:

1. 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.
2. 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.
3. 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.
4. 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:

#include <stdio.h>

int findMajorityElement(int arr[], int size, int n) {
    int candidate[n - 1];
    int count[n - 1];

    for (int i = 0; i < n - 1; i++) {
        candidate[i] = -1;
        count[i] = 0;
    }

    for (int i = 0; i < size; i++) {
        int j;
        for (j = 0; j < n - 1; j++) {
            if (arr[i] == candidate[j]) {
                count[j]++;
                break;
            }
        }
        if (j == n - 1) {
            int k;
            for (k = 0; k < n - 1; k++) {
                if (count[k] == 0) {
                    candidate[k] = arr[i];
                    count[k] = 1;
                    break;
                }
            }
            if (k == n - 1) {
                for (k = 0; k < n - 1; k++) {
                    count[k]--;
                }
            }
        }
    }

    // Validate whether each candidate appears more than size/n times
    int freq = 0;
    for (int i = 0; i < n - 1; i++) {
        int count = 0;
        for (int j = 0; j < size; j++) {
            if (arr[j] == candidate[i]) {
                count++;
            }
        }
        if (count > size / n) {
            freq++;
            printf("The element appearing more than %d-th of the total is: %d\n", n, candidate[i]);
        }
    }

    if (freq == 0) {
        printf("No element appearing more than %d-th of the total\n", n);
    }

    return 0;
}

int main() {
    int arr[] = {2, 4, 2, 2, 5, 2, 2, 6, 2, 2, 8, 3, 3, 3, 3};


 int size = sizeof(arr) / sizeof(arr[0]);
    int n = 4;

    findMajorityElement(arr, size, n);

    return 0;
}

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:

The element appearing more than 4-th of the total is: 2
The element appearing more than 4-th of the total is: 3