Grade 9 · Frequency arrays, prefix sums and the Sieve of EratosthenesCitește în română

Majority element

Original: Elementul majoritar

O(n)C++1773 lines2 examples

The idea

The majority element appears more than n / 2 times. The voting algorithm (Boyer-Moore) keeps a candidate and a counter: an element equal to the candidate increases the counter, a different one decreases it, and when the counter reaches 0 the current element becomes the new candidate. Different values 'cancel out' in pairs, so only the majority can remain. At the end we count the candidate's occurrences, because there may be no majority.

Original description (Romanian)

Elementul majoritar apare de mai mult de n / 2 ori. Algoritmul prin vot (Boyer-Moore) păstrează un candidat și un contor: un element egal cu candidatul crește contorul, unul diferit îl scade, iar la contor 0 elementul curent devine noul candidat. Valorile diferite se „anulează” în perechi, deci doar majoritarul poate rămâne. La final numărăm aparițiile candidatului, pentru că s-ar putea să nu existe majoritar.

Complexity
O(n), with no limit on the size of the values
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

7
2 3 2 2 5 2 2

Expected output

2
Example 2

Input

4
1 2 1 2

Expected output

NU

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

element-majoritar.cpp
/*
 * Titlu: Elementul majoritar
 * Clasa: 9
 * Capitol: Frecvență, sume parțiale și ciurul lui Eratostene
 * Descriere: Elementul majoritar apare de mai mult de n / 2 ori. Algoritmul prin
 *            vot (Boyer-Moore) păstrează un candidat și un contor: un element egal
 *            cu candidatul crește contorul, unul diferit îl scade, iar la contor 0
 *            elementul curent devine noul candidat. Valorile diferite se „anulează”
 *            în perechi, deci doar majoritarul poate rămâne. La final numărăm
 *            aparițiile candidatului, pentru că s-ar putea să nu existe majoritar.
 * Complexitate: O(n), fără limită pentru mărimea valorilor
 *
 * Exemplu
 * Intrare:
 * 7
 * 2 3 2 2 5 2 2
 * Ieșire: 2
 *
 * Exemplu
 * Intrare:
 * 4
 * 1 2 1 2
 * Ieșire: NU
 */
#include <iostream>
using namespace std;

int v[100001];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    int candidat = v[1], contor = 0;
    for (int i = 1; i <= n; i++)
    {
        if (contor == 0)
        {
            candidat = v[i];
            contor = 1;
        }
        else if (v[i] == candidat)
        {
            contor++;
        }
        else
        {
            contor--;
        }
    }
    int aparitii = 0;
    for (int i = 1; i <= n; i++)
    {
        if (v[i] == candidat)
        {
            aparitii++;
        }
    }
    if (aparitii > n / 2)
    {
        cout << candidat << '\n';
    }
    else
    {
        cout << "NU" << '\n';
    }
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.