Задача
Найдите число, которое встречается в последовательности нечетное количество раз.
Входные данные
Первая строка содержит натуральное число $n (n < 500000)$. Далее следуют $n$ натуральных чисел, каждое из которых меньше $10^6$.
Выходные данные
Во входной последовательности только одно число $x$ повторяется нечетное количество раз. Другие числа повторяются четное число раз. Выведите $x$.
Замечание
В условии задачи на e-olymp опечатка, но, проанализировав входные и выходные данные примеров, несложно понять суть задачи.
Тесты
| № | Ввод | Вывод |
| 1 | 9 3 1 2 2 17 1 3 17 3 |
3 |
| 2 | 5 12 13 14 13 12 |
14 |
| 3 | 3 20 0 20 |
0 |
| 4 | 15 5 7 1 2 3 5 7 2 7 5 1 2 3 5 2 |
7 |
| 5 | 11 10 100 1000 100 100 100 1000 10 100 1000 100 |
1000 |
Код 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <iostream> #include <algorithm> using namespace std; int main() { long long n, *x; cin >> n; x = new long long[n]; for (int i = 0; i < n; i++) cin >> x[i]; sort(x, x + n); long long k, y; k = 1; y = x[0]; for (int i = 1; i < n; i++) { if (x[i] == y) k++; else { if (k % 2 != 0) { cout << y; return 0; } else { k = 1; y = x[i]; } } } cout << x[n - 1]; delete []x; return 0; } |
Код 2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> using namespace std; int main() { long long n, *x; cin >> n; x = new long long[n]; for (int i = 0; i < n; i++) cin >> x[i]; long res = 0; for (int i = 0; i < n; i++) res ^= x[i]; cout << res; delete []x; return 0; } |
Код 3 (без массива)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> using namespace std; int main() { long long n, res = 0, x; cin >> n; for (int i = 0; i < n; i++) { cin >> x; res ^= x; } cout << res; return 0; } |
Решение
Для начала создадим динамический одномерный массив и считаем с потока ввода все его элементы. Конечно, можно было создать статический массив на 500000 элементов, но, скорее всего, памяти выделилось бы намного больше, чем было бы использовано.
Первый способ
Отсортируем наш массив по возрастанию. Как будем сортировать особо значения не имеет, главное, чтоб одинаковые элементы стояли подряд.
Затем, заведём две переменные: счётчик и число. Последней присваиваем значение первого элемента массива. Сравниваем следующий элемент с тем, что лежит в переменной. Если они равны, увеличиваем счетчик. В счетчик с самого начала положим единицу, так как предполагаем, что в массиве есть хоть один элемент.
Как только проверяемый нами элемент массива не будет равен значению переменной, проверяем счетчик на четность. Если нечетный, выводим значение переменной и завершаем работу программы. Если четный, присваиваем переменной новое значение, а счетчику снова единицу. Так будем подсчитывать пока не найдём число, повторяющееся нечетное количество раз. Если не найдем, это значит, что искомое число последнее, так как оно обязательно есть по условию, а наша программа сработает для всех элементов, кроме последнего (последний элемент мы не можем сравнить со следующим, а значит не можем проверить счетчик).
Второй способ
Применим исключающее «или» ко всем элементам массива. Предварительно создадим переменную равную нулю, в которой будем это проделывать.
Так как xor двух одинаковых чисел равен нулю, то для любого количества пар одинаковых чисел он будет равен нулю. А вот xor нуля и любого числа равен самому числу.
Таким образом, исключив все пары одинаковых чисел, наша переменная примет значение повторяющегося нечетное количество раз числа.
Третий способ
Идейно такой же как предыдущий. Отличается только тем, что мы не записываем числа в массив, а исключающее «или» работает сразу после того как число было прочитано.