Majority Element

Given an array A of N elements. Find the majority element in the array. A majority element in an array A of size N is an element that appears more than N/2 times in the array.

• Time : O(n)
• Space : O(1)

int majorityElement(int a[], int size) {
    int res = -1, count = 0;
    for(int i = 0; i < size; i++) {
        if(a[i] == res) count++;
        else if(count == 0) {
            count++;
            res = a[i];
        } else count--;
    }
    count = 0;
    for(int i = 0; i < size; i++) {
        if(a[i] == res) count++;
    }

    return count * 2 > size ? res : -1;
}