Забавные задачки

[Товарищ ♂uatr]

У Яндекса ранее была задачка: найти массиве, состоящем из нечетного количества элементов, уникальное число за время О(n). В рамках условия гарантируется, что только искомое число не имеет парного повторения. Т.е. [1,1,-1,-1,5]. Искомым числом здесь будет 5.

[axm2017]

Цитата:

Сообщение от Товарищ ♂uatr

У Яндекса ранее была задачка: найти массиве, состоящем из нечетного количества элементов, уникальное число за время О(n). В рамках условия гарантируется, что только искомое число не имеет парного повторения. Т.е. [1,1,-1,-1,5]. Искомым числом здесь будет 5.

последовательности записаны целые числа. Одно из чисел встречается ровно один раз, остальные — по два раза. Найти число, которое встречается один раз.
Видимо это?
Здесь тоже всё просто: найдем XOR всех чисел — он и будет ответом. В самом деле, если какой-то бит в искомом числе равен нулю, то во всей последовательности он будет равен 1 в чётном числе элементов, и его значение в XOR равно нулю. В противном случае, аналогично, его значение в XOR равно 1. Или, проще говоря, одинаковые элементы при суммировании взаимоуничтожатся.

[axm2017]

Цитата:

Сообщение от Товарищ ♂uatr

У Яндекса ранее была задачка: найти массиве, состоящем из нечетного количества элементов, уникальное число за время О(n). В рамках условия гарантируется, что только искомое число не имеет парного повторения. Т.е. [1,1,-1,-1,5]. Искомым числом здесь будет 5.

Видимо это?
Здесь тоже всё просто: найдем XOR всех чисел — он и будет ответом. В самом деле, если какой-то бит в искомом числе равен нулю, то во всей последовательности он будет равен 1 в чётном числе элементов, и его значение в XOR равно нулю. В противном случае, аналогично, его значение в XOR равно 1. Или, проще говоря, одинаковые элементы при суммировании взаимоуничтожатся.