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).

If the count (frequency of occurrences) array is used to look for the majority element, then the absolute majority element would be the index of the count array whose frequency is more than n/2 (integer division). 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.

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.

Note:

Actually, the absolute majority element differs from the majority element. Absolute majority means more than half, and it refers to the element whose frequency of occurrence is more than half of the total number of elements. Majority element simply refers to the element with highest frequency of occurrence and not necessarily more than half. In the last example above, 6 is the absolute majority element, as well as it is the majority element.

A list may have a majority element but not necessarily the absolute majority element. In the following list, 7 is the majority element and not the absolute majority element.

    [9, 9, 8, 8, 7, 7, 7, 7]

The frequency of 7 is 4, which is more than floor n/3 (8/3 = 2). So 7 is the majority element II. The order of element arrangement in the list, does not matter.

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.

Note: The returned array of majority elements should be sorted.

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+m) time.

Note:

Note: Solving this problem the brute-force (naive) way will take n² time, and that approach is not recommended.

Strategy

Produce a count array for each of the elements in the given list in O(n) time. Iterate over the count array in O(m) time looking for the elements (index) with frequency that is higher than n/3. The length of the count array is actually m+1, where m is the biggest value in the given array. The +1 for the length is just in case the list has an element with value 0 (it is the convenience 0 if the given list does not have an element with value 0, because array counting begins from 0, for zero-based counting).

If the count frequency of occurrences scheme is used, then the elements found in the count array will be in ascending order.

The O(n+m) Program

The program is as follows, where voted1 and voted2 are the possible frequencies asked for (read through the code and comments):

#include <stdio.h>

void solution(int A[], int n, int m) {
    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;
    }
    
    int voted1 = -1;
    int voted2 = -1;
    
    for (int i=0; i < m+1; i++) {    //looking for indexes with freq > n/3
        if (count[i] > n/3) {
            if (voted1 == -1) 
                voted1 = i; 
            else 
                voted2 = i;
        }
    }

    if (voted1 == -1)
        printf("-1");
    else {
        if (voted1 != -1)
            printf("%i ", voted1);
        if (voted2 != -1)
            printf("%i ", voted2);
    }
    
    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:

    1 2 
    5 
    -1
    6 

and correct.

The time complexity for the called function is O(n+m), with n being the time to iterate over the given array and m being the time to iterate over the count array, looking for any frequency that is greater than n/3. The time to initialize the count array elements to 0 is ignored. Any O(1) time is also ignored. The space complexity for the called function is O(n+m) for the given and count array. The given array is produced outside the called function, but it is also used inside the called function. Any O(1) space in the called function is also ignored.

Thanks for reading.