Cerința

Se dă un vector cu n elemente, numere naturale. Verificați dacă vectorul are un element majoritar. Numim element majoritar o valoare pentru care numărul de apariții în vector este mai mare decât n/2.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând elementele vectorului.

Date de ieșire

Programul va afișa pe ecran mesajul NU, dacă vectorul nu are un element majoritar, respectiv DA X, dacă vectorul are un element majoritar, unde X este valoarea acestuia.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• cele n numere citite vor fi mai mici decât 1.000.000.000

Exemplu

Intrare

10
5 2 1 5 3 5 5 1 5 5

Ieșire

DA 5

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n , a[100001] , c , f;
    cin >> n >> a[1];
    c=a[1]; ///candidatu
    f = 1;///frecventa pro-votur contra
    for(int i= 2 ; i <= n ; ++i)
    {
        cin >> a[i];
        if(a[i] == c) f++;///vot pro
        else
        {
            f--;///vot contra
            if(f == 0)/// schimb candidatul
            {
                c = a[i];
                f = 1;
            }
        }
    }
    f = 0;for(int i = 1 ; i <= n ; ++i) /// verific daca e majoritar
    if(a[i] == c) f++;
    if(f > n/2) cout << "DA" <<" " << c;
    else cout << "NU";
}