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

Frequency array

Original: Vectorul de frecvență

O(n)C++1743 lines1 example

The idea

For small natural values (here 0..1000), frecv[x] stores how many times the value x has appeared. The value becomes an index, so every number read is counted in a single step. At the end we find the most frequent value (the smallest one, on ties) and its frequency.

Original description (Romanian)

Pentru valori naturale mici (aici 0..1000), frecv[x] reține de câte ori a apărut valoarea x. Valoarea devine indice, așa că fiecare număr citit se numără într-un singur pas. La final aflăm valoarea care apare cel mai des (cea mai mică, la egalitate) și frecvența ei.

Complexity
O(n + V), where V is the largest possible value
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

8
3 7 3 1 7 3 9 1

Expected output

3 3

The code

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

vector-de-frecventa.cpp
/*
 * Titlu: Vectorul de frecvență
 * Clasa: 9
 * Capitol: Frecvență, sume parțiale și ciurul lui Eratostene
 * Descriere: Pentru valori naturale mici (aici 0..1000), frecv[x] reține de câte
 *            ori a apărut valoarea x. Valoarea devine indice, așa că fiecare
 *            număr citit se numără într-un singur pas. La final aflăm valoarea
 *            care apare cel mai des (cea mai mică, la egalitate) și frecvența ei.
 * Complexitate: O(n + V), unde V este valoarea maximă posibilă
 *
 * Exemplu
 * Intrare:
 * 8
 * 3 7 3 1 7 3 9 1
 * Ieșire: 3 3
 */
#include <iostream>
using namespace std;

const int VMAX = 1000;
int frecv[VMAX + 1];

int main()
{
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        frecv[x]++;
    }
    int valoare = 0;
    for (int val = 1; val <= VMAX; val++)
    {
        if (frecv[val] > frecv[valoare])
        {
            valoare = val;
        }
    }
    cout << valoare << ' ' << frecv[valoare] << '\n';
    return 0;
}

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