e-olymp 8374. Нечетное количество раз

Задача 

Найдите число, которое встречается в последовательности нечетное количество раз.

Входные данные

Первая строка содержит натуральное число $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

Код 2

Код 3 (без массива)

 

Решение

Для начала создадим динамический одномерный массив и считаем с потока ввода все его элементы. Конечно, можно было создать статический массив на 500000 элементов, но, скорее всего, памяти выделилось бы намного больше, чем было бы использовано.

Первый способ

Отсортируем наш массив по возрастанию. Как будем сортировать особо значения не имеет, главное, чтоб одинаковые элементы стояли подряд. 

Затем, заведём две переменные: счётчик и число. Последней присваиваем значение первого элемента массива. Сравниваем следующий элемент с тем, что лежит в переменной. Если они равны, увеличиваем счетчик. В счетчик с самого начала положим единицу, так как предполагаем, что в массиве есть хоть один элемент.

Как только проверяемый нами элемент массива не будет равен значению переменной, проверяем счетчик на четность. Если нечетный, выводим значение переменной и завершаем работу программы. Если четный, присваиваем переменной новое значение, а счетчику снова единицу. Так будем подсчитывать пока не найдём число, повторяющееся нечетное количество раз. Если не найдем, это значит,  что искомое число последнее, так как оно обязательно есть по условию, а наша программа сработает для всех элементов, кроме последнего (последний элемент мы не можем сравнить со следующим, а значит не можем проверить счетчик).

Второй способ

Применим исключающее «или» ко всем элементам массива. Предварительно создадим переменную равную нулю, в которой будем это проделывать. 

Так как xor двух одинаковых чисел равен нулю, то для любого количества пар одинаковых чисел он будет  равен нулю. А вот xor нуля и любого числа равен самому числу.

Таким образом, исключив все пары одинаковых чисел, наша переменная примет значение повторяющегося нечетное количество раз числа. 

Третий способ 

Идейно такой же как предыдущий. Отличается только тем, что мы не записываем числа в массив, а исключающее «или» работает сразу после того как число было прочитано.

Ссылки

Задача 8374 на e-olymp

Код 1 на Ideone

Код 2 на Ideone

Related Images:

7 thoughts on “e-olymp 8374. Нечетное количество раз

  1. Данное решение работает за $O\left(n \cdot \log n\right)$, в то время как существуют решения, работающие за $O\left(d\right)$, где $d$ — размер диапазона вводимых чисел, и даже за $O\left(n\right)$ без использования сортировки и массива. Прошу Вас подумать об этих решениях.

    • Большое спасибо, что обратили внимание на это. Всё дело в том, что данная задача из пятой темы, а она посвящена массивам. Мне необходимо было написать код с их использованием. Но об оптимизации обещаю подумать 🙂

    • В наших условиях выходит, что $O\left(d\right)$ несколько лучше,чем $O\left(n\cdot\log n\right)$ и массивы пригодятся в этом случае. Так что подумайте.

  2. Не удаляйте это решение, когда придумаете другое.
    Возможно нужно задуматься о массиве логических переменных для каждого из миллиона чисел? Я имею в виду следить за тем, встретилось ли число нечетное число раз.
    Извините, а какая опечатка в условии на сайте? В смысле, что нужно найти число, которое встречается нечетное количество раз, а не только один раз? Похоже, что Вы правы. Думаю стоит написать комментарий к этой задаче прямо на сайте e-olymp.

    • Спасибо, всё сделала 🙂
      А по поводу миллиона чисел, думаю, если зациклить считывание их с потока ввода и xor должно получиться. Данную задачу и правда можно решить намного проще и без массива, но код я опубликовала под предполагаемые входные данные (с количеством элементов) и с массивом, как требует тема.
      Код, описанный выше

    • Вы совершенно правы. Этот вариант гораздо лучше. И массив никакой не нужен. Молодец!
      Опубликуйте его в работе. Не страшно, что тема с массивами.
      Только читайте входные данные не до конца потока, а заданное число раз.

Добавить комментарий