#include <stdio.h>

int findCandidate(int *, int);
int isMajority(int *, int, int);

int main() {
    int arr[] = {34,15,34,34,34,34,15,15,34,34,22,15,15,15,15,34,15,34,15,15,34,15,34,15,34,22,22,15,34,15,34,15,34,15,34,22,34,22,34,34,34,34,34,22,15,34,34,34,15,34,15,15,22,34,15,15,34,34,34,22,34,15,15,34,34,34,15,22,22,22,15,34,34,22,34,34,22,34,15,22,34,34,15,22,34,34,34,34,22,22,15,34,34,22,34,34,34,22,34,22};
    int size = sizeof(arr)/sizeof(int);
    int candidate = findCandidate(arr, size);
    int majority = isMajority(arr, size, candidate);
    printf("size: %d, candidate: %d, majority: %d", size, candidate, majority);
    return 0;
}

int findCandidate(int * arr, int size) {
    int majIdx = 0, count = 1, i;
    for(i = 1; i < size; i++) {
        if (count == 0) {
            majIdx = i;
            count = 1;
            continue;
        }

        if (arr[majIdx] == arr[i])
            count++;
        else
            count--;
    }

    if(count == 0)
        return -1;

    return arr[majIdx];
}

int isMajority(int * arr, int size, int candidate) {
    int i, count = 0;
    for(i = 0; i < size; i++) {
        if(arr[i] == candidate)
            count++;
    }

    if(count > size/2)
        return 1;

    return 0;

}