#include <iostream>
#include <ctime>
#include <cstdlib>
#include <fstream>
using namespace std;

int znajdzKandydata(int a[], int rozmiar)
{
    int maj_index = 0; //numer indeksu liczby dominujacej
    int count = 1;
    int i;
    for(i=1; i<rozmiar; i++)
    {
        if(a[maj_index] == a[i])
            count++;
        else
            count--;
        if(count == 0)
        {
            maj_index = i;
            count = 1;
        }
    }
    return a[maj_index];
}

bool czyDominujacy(int a[], int rozmiar, int kand)
{
    int i;
    int count = 0;
    for(i=0; i<rozmiar; i++)
        if(a[i]==kand)
            count++;
    if(count>rozmiar/2)
        return 1;
    else
        return 0;
}

void wypiszDominujaca(int a[], int rozmiar)
{
    int kand = znajdzKandydata(a, rozmiar);
    if(czyDominujacy(a, rozmiar, kand))
    {
       cout << "Element domunujacy to: "<<kand<<endl;
    }
    else
        cout << "Brak elementu dominujacego \n";
}

int main()
{
    srand(time(NULL));
    int n, i, k;
    cout << "Podaj rozmiar tablicy " << endl;
    cin >> n;
    int tab[n];
    string nazwa = "wynik.txt";
    ofstream wyjscie(nazwa.c_str());
    for(k=0; k<=n; k+=1000)
    {
        for(i=0; i<k; i++)
        {
            tab[i] = rand()%2;
            //cout << tab[i] << " ";
        }
        cout << endl;
        clock_t start, koniec;
        start = clock();
        wypiszDominujaca(tab, k);
        koniec = clock();
        long delta = (long)(koniec - start);
        cout << "Czas wykonania operacji to " << delta << "s";
        cout<<"\n";
        wyjscie << k << " Czas Trwania: " << delta << ";" << endl;
    }
    return 0;
}