1. Идея

Нужно просто посчитать, сколько элементов массива равны числу x.

Для этого достаточно:

• прочитать все n чисел;
• завести переменную count = 0;
• пройти по массиву;
• каждый раз, когда очередной элемент равен x, увеличивать count на 1.

В конце выводим count.

2. Наблюдения

1. Нас не интересуют позиции элементов, только их количество.
2. Никакая сложная структура данных не нужна.
3. Ограничение n <= 2 * 10^5 легко позволяет один линейный проход по массиву.
4. Значения a_i и x могут быть отрицательными, но это никак не влияет на решение: сравнение на равенство работает одинаково для любых целых чисел.

3. Алгоритм

1. Считать число n.
2. Считать массив из n целых чисел.
3. Считать число x.
4. Создать переменную count и присвоить ей 0.
5. Пройти по всем элементам массива:
   • если текущий элемент равен x, увеличить count на 1.
6. Вывести count.

4. Почему это работает

Рассмотрим каждый элемент массива по очереди.

• Если элемент равен x, то он является одним из вхождений x, и его нужно учесть. Поэтому увеличиваем count.
• Если элемент не равен x, то он не должен влиять на ответ, и мы ничего не делаем.

Так как мы просматриваем все элементы массива ровно один раз, ни одно вхождение x не будет пропущено.
И наоборот, в count попадут только те элементы, которые действительно равны x.

Значит, после завершения прохода переменная count будет точно равна количеству вхождений числа x в массив.

5. Сложность

• Время: O(n), потому что массив просматривается один раз.
• Память: O(n) в приведённых решениях, так как элементы сохраняются в массиве или списке.

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long *a = new long long[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long x;
    cin >> x;

    int count = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == x) {
            count++;
        }
    }

    cout << count << '\n';

    delete[] a;
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))
x = int(input())

count = 0
for value in a:
    if value == x:
        count += 1

print(count)