// Laboratorio 3 - Esercizio 1
// Matteo Schiff - s295565

#include <stdio.h>
#include <stdlib.h>

int majority(int * a, int N) {
    if (N == 1) {
        return a[0];
    }

    int m = N/2;

    int x = majority(a, m);
    int y = majority(a+m, m);

    if (x == y)
        return x;

    if (x != -1) {
        int c = 0;
        for (int i = 0; i < N; i++) {
            if (a[i] == x)
                c++;
        }
        if (c > (N/2))
            return x;
    }

    if (y != -1) {
        int c = 0;
        for (int i = 0; i < N; i++) {
            if (a[i] == y)
                c++;
        }

        if (c > (N/2))
            return y;
    }

    return -1;
}

int main(int argc, char ** argv) {
    int N = argc - 1;

    if (argc < 2)
        return 1;

    int * vec = malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) {
        vec[i] = atoi(argv[i+1]);
    }

    printf("major: %d\n", majority(vec, N));
}