The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Integer Division or Flooring the Quotient

Integer Division or Flooring the Quotient, are very similar things. Consider the following statement:

    Dividend / Divisor = Quotient

The dividend and divisor are whole numbers. The quotient consists of the whole number and a remainder. The remainder can be 0. With integer division, only the whole number part of the quotient is taken and the remainder is abandoned. It does not matter if the remainder is more than half the whole number part, or less, or equal to half. For example 8 / 3 = 2 remainder 2. Here the remainder, 2 is abandoned and the whole number of 2 is taken. As another example, 9 / 3 = 3 remainder 0. Here the remainder, 0 is abandoned and 3 is taken.

As other examples: 5 / 3 = 1R2 = 1; 4 / 3 = 1R1 = 1; 3 / 3 = 1R0 = 1; 2 / 3 = 0R2 = 0; 1 / 3 = 0R1 = 0; 0 / 0 = 0R0 = 0.

Meaning of Majority Element I

In a list of n elements, the element that occurs more than n/2 times is the majority element I. This is actually the absolute majority and not just the majority. n/2 is the integer division (see below).

Meaning of Majority Element II

In a list of n elements, the element that occurs more than n/3 times is the majority element II. There can be one or at most two of such elements. The reader should verify that out, on his/her own. If there are two of such elements, then they are two different elements and their numbers or their frequencies, would not necessarily be the same. The two elements cannot be the same, because if they are the same, then that is majority element I; OR both majority elements II are the same as the majority element I.

Neither of these two elements can be majority element I, officially. When there are two different elements that occur more than n/3 of the times, then there is no majority element I. n/3 is integer division. Note: it is possible for a list to have neither majority element I nor majority element II.

If the count (frequency of occurrences) array is used to look for the majority elements II, then the elements (one or two) with the highest frequencies, with each greater than n/3, are the answers. Do not forget that in the count array, each index is a value in the given array. A value in the count array is the number of occurrences of that index, as value, in the given array.

This tutorial deals with majority element II.

Since the approach that uses the count array takes O(n+m) time, that approach will not be used here. A O(n) approach will be used (see below).

Illustration for the Algorithm of Boyer and Moore

Consider the following input array:

    A[] = [2, 2, 3, 1, 3, 2, 1, 1]

By inspection, 2 and 1 are the majority elements II, with each frequency greater than n/3.

For the purpose of analysis, assume that the first element, 2 is for the first majority element II, and the third element 3 is for the second majority element II. For this array, the first element happens to be one of the majority elements II, but this is not always the case. The first element does not necessarily have to be one of the majority elements II. An element assumed like that is called the candidate. There are two candidates for this algorithm which should not be the same at the end of the algorithm. The corresponding variables are candidate1 and candidate2. If they are the same at the end of the algorithm, then it is majority element I that is looked for, and not majority element II.

Let the value of the counter for the first candidate be called voteCount1, which was initially set to 1. Let the value of the counter for the second candidate be called voteCount2, which was initially set to 1. Continue to iterate over the array.

The next alternate elements, are 2 and 1. Two should be compared to candidate1 which is 2; and 1 should be compared to candidate2 which is 3. The first comparison shows equality and the second comparison does not show equality, so increment voteCount1 from 1 to 2, and decrement voteCount2 from 1 to 0. As voteCount2 has just become 0, candidate2 becomes 1 and voteCount2 is reset to 1. candidate1 remains at 2 and its voteCount1 is 2.

The next alternate elements, are 3 and 3. The first 3 should be compared to candidate1 which is 2; and the second 3 should be compared to candidate2 which is 1. Neither comparisons this time shows equality; so decrement voteCount1 from 2 to 1, and decrement voteCount2 from 1 to 0. As voteCount2 has just become 0, candidate2 becomes 3 and voteCount2 is reset to 1. candidate1 remains at 2 but its voteCount1 is now 1.

The next alternate elements, are 1 and 2. The 1 should be compared to candidate1 which is still 2; and the 2 should be compared to candidate2 which is 3. Neither comparisons this time shows equality; so decrement voteCount1 from 1 to 0, and decrement voteCount2 from 1 to 0. As voteCount1 has just become 0, candidate1 becomes 1 and voteCount1 is reset to 1. As voteCount2 has just become 0, candidate2 becomes 2 and voteCount2 is reset to 1.

The next alternate elements, are 3 and 1. The 3 should be compared to candidate1 which is 1; and the 1 should be compared to candidate2 which is 2. Neither comparisons this time shows equality; so decrement voteCount1 from 1 to 0, and decrement voteCount2 from 1 to 0. As voteCount1 has just become 0, candidate1 becomes 3 and voteCount1 is reset to 1. As voteCount2 has just become 0, candidate2 becomes 1 and voteCount2 is reset to 1.

The next alternate elements, are 2 and 1. The 2 should be compared to candidate1 which is 3; and the 1 should be compared to candidate2 which is 1. The comparison of 2 and 3 are not the same so decrement voteCount1 from 1 to 0. The second comparison of 1 and 1 are the same so increment voteCount2 from 1 to 2. As voteCount1 has just become 0, candidate1 becomes 2 and voteCount1 is reset to 1. candidate2 remains at 1 and voteCount2 is 2.

The first iteration of the algorithm ends. Candidate1 = 2 and candidate2 = 1. voteCount1 = 1 (a somewhat temporary frequency). voteCount2 = 2 (another somewhat temporary frequency).

Each vote count will always end up with at least a value of 1.

Second Iteration

At this point the value of each candidate is a hint that, that value occurs at least n/3 times. The hint is not a guarantee. For any vote count that is greater than 1, a second iteration over the whole given array is necessary, to know if its candidate occurs more than n/3 times. Both candidates can be verified in one for-loop. It might end up that both candidates occurs more than n/3 times each, or one candidate occurs more than n/3 times and the other does not, or neither candidate occurs more than n/3 times.

Edge Cases

This algorithm works without a problem, when the length, n of the given array is at least 4.

When the length, n is 0, n/3 = 0/3 = 0 (integer division).
In this case, just return -1 or display null, for nothing.

When the length, n is 1, n/3 = 1/3 = 0 (integer division).
In this case, just return or display the single value, as 1 is greater than 0.

When the length, n is 2, n/3 = 2/3 = 0 (integer division).
In this case, return or display each of the values, as 1 is greater than 0; it does not matter if the two values are the same.

When the length, n is 3, n/3 = 3/3 = 1 (integer division).
In this case, use the count array for frequency-of-occurrences approach. Then return or display the element with the frequency that is greater than 1, as 2 or 3 is greater than 1; it does not matter if the elements are the same.

Boyer-Moore Majority Vote Algorithm

The algorithm is based on the fact that if one element occurs more than n/3 times, and another occurs more than n/3 times, then all the remaining elements together must occur in less than "n/3 + n/3" times.

While traversing the array, two candidates are maintained and two corresponding vote counts are also maintained:

- If the current element matches a candidate, increment its vote count.
- If it does not match, decrement its vote count.
- When the vote count becomes 0, it means the previous candidate cannot be the majority element, so select the current element as the new candidate, incrementing the vote count to 1.

By the end of the first traversal, the remaining candidates are the potential majority elements II. A second traversal is required to verify whether both actually appear more than n/3 times.

At the end of the array (first pass) a vote count will always be at least 1.

Problem

Given an array A[] consisting of n integers, find all the array elements which occur more than floor(n/3) times. If no such element exists, return -1.

Examples:

Input: arr[] = [2, 2, 3, 1, 3, 2, 1, 1]
Output: [1, 2]
Explanation: The frequency of 1 and 2 is 3, which is more than floor n/3 (8/3 = 2).

Input: arr[] = [5, 3, 5]
Output: [5]
Explanation: The frequency of 5 is 2, which is more than floor n/3 (3/3 = 1).

Input: arr[] = [3, 2, 2, 4, 1, 4]
Output: [ ] //empty set
Explanation: There is no majority element.

Input: arr[] = [6, 4, 5, 6, 6, 5 ,6, 6]
Output: [6]
Explanation: The frequency of 6 is 5, which is more than floor n/3 (8/3 = 2).

Solve the problem in O(n) time, using Boyer-Moore Majority Vote Algorithm.

The O(n) Program

The program is (read through the code and comments):

#include <stdio.h>

void solution(int A[], int n, int m) {    
    //Edge Cases
    if (n == 0) {
        printf("null\n"); return;}
    else if (n == 1) {
        printf("%i\n", A[0]); return;}
    else if (n == 2) {
        printf("%i, ", A[0]); printf("%i", A[1]); printf("\n"); return;}
    else if (n == 3) {
        int count[m+1];
        for (int i=0; i < m+1; i++)
            count[i] = 0;    //initializing count array
    
        for (int i=0; i < n; i++){
            count[A[i]] += 1;   //same as count[A[i]] = count[A[i]] + 1;
        }
    
        for (int i=0; i < m+1; i++){    //looking for index with freq > 3/3 = 1
            if (count[i] > n/3) {
                printf("%i\n", i); return;}
        }

        printf("%i\n", -1); return;  //if no element in given array has freq > 3/3 = 1
    }
    
    //Boyer-Moore's algorithm begins
    int candidate1 = A[0];
    int candidate2 = A[0+2];
    int voteCount1 = 1;
    int voteCount2 = 1;
    
    //first pass
    for (int i=1; i < n-2; i++){
        //for candidate1
        if (candidate1 == A[i])
            voteCount1 = voteCount1 + 1;
        else
            voteCount1 = voteCount1 - 1;
            
        if (voteCount1 == 0) {
            candidate1 = A[i]; voteCount1 = 1;
        }
        //for candidate2
        if (candidate2 == A[i+2])
            voteCount2 = voteCount2 + 1;
        else
            voteCount2 = voteCount2 - 1;
            
        if (voteCount2 == 0) {
            candidate2 = A[i+2]; voteCount2 = 1;
        }
    }

    //second pass
    int frequency1 = 0;
    int frequency2 = 0;
    for (int i=0; i < n; i++){    //looking for candidate with freq > n/3
        if (A[i] == candidate1)
            frequency1++;
        if (A[i] == candidate2)
            frequency2++;
    }

    if (frequency1 > n/3)
        printf("%i, ", candidate1);
    if (frequency2 > n/3)
        printf("%i", candidate2);
        
    if (!(frequency1 > n/3) && !(frequency2 > n/3))
        printf("-1");
    
    printf("\n");
}
  
int main(int argc, char **argv) 
{
    int A1[] = {2, 2, 3, 1, 3, 2, 1, 1};
    int n1 = sizeof(A1) / sizeof(A1[0]);    //length of given array
    int m1 = 0;
    for (int i=0; i < n1; i++)
        if (A1[i] > m1)
            m1 = A1[i];
    solution(A1, n1, m1);
    
    int A2[] = {5, 3, 5};
    int n2 = sizeof(A2) / sizeof(A2[0]);    //length of given array
    int m2 = 0;
    for (int i=0; i < n2; i++)
        if (A2[i] > m2)
            m2 = A2[i];
    solution(A2, n2, m2);
    
    int A3[] = {3, 2, 2, 4, 1, 4};
    int n3 = sizeof(A3) / sizeof(A3[0]);    //length of given array
    int m3 = 0;
    for (int i=0; i < n3; i++)
        if (A3[i] > m3)
            m3 = A3[i];
    solution(A3, n3, m3);
    
    int A4[] = {6, 4, 5, 6, 6, 5 ,6, 6};
    int n4 = sizeof(A4) / sizeof(A4[0]);    //length of given array
    int m4 = 0;
    for (int i=0; i < n4; i++)
        if (A4[i] > m4)
            m4 = A4[i];
    solution(A4, n4, m4);
    
    return 0; 
}

The output is:

    2, 1
    5
    -1
    6, 6    //majority element I of > n/2 is 6

The time complexity for the called function is actually O(2n), with the first n for the first pass and the second n for the second pass. The coefficient (multiplicand of 2) is usually omitted to quote a time complexity of O(n). The time complexities for the edge cases are ignored. The space complexity for the called function is O(n) for the given array. The given array is produced outside called function, but it is also used inside the called function. The space complexities for the edge cases are ignored.

Thanks for reading.