Element Majoritari X61571


Statement
 

pdf   zip

html

Donat un conjunt de n números diem que un número és l’element majoritari si apareix més de n/2 vegades. Donat un conjunt de números, digueu si hi ha element majoritari, en cas que n’hi hagi indiqueu quin és.

Entrada

L’entrada consisteix en diversos casos, hi ha com a molt 200 casos. Cada cas consta de dues línies, la primera conté un enter 1 ≤ n ≤ 105, la mida del conjunt. La segona línia conté els n números del conjunt, ai amb 1 ≤ ai ≤ 109. La suma de la mida de tots els conjunts és menor que 5·105.

Sortida

Escriviu un enter per línia: l’element majoritari. En cas que no existeixi tal element escriviu "Sense solucio".

Public test cases

  • Input

    8
3 3 3 4 4 4 4 4 
6
1 1 2 1 1 2
6
1 2 3 4 5 6
4
1 1 2 2
5
1 1 1 2 2

    Output

    4
1
Sense solucio
Sense solucio
1
    • Information
    Author
    Max Balsells
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++