|
08.04.2024, 18:36 | #1 |
Участник
|
У Яндекса ранее была задачка: найти массиве, состоящем из нечетного количества элементов, уникальное число за время О(n). В рамках условия гарантируется, что только искомое число не имеет парного повторения. Т.е. [1,1,-1,-1,5]. Искомым числом здесь будет 5.
|
|
11.04.2024, 01:23 | #2 |
Участник
|
Цитата:
Видимо это? Здесь тоже всё просто: найдем XOR всех чисел — он и будет ответом. В самом деле, если какой-то бит в искомом числе равен нулю, то во всей последовательности он будет равен 1 в чётном числе элементов, и его значение в XOR равно нулю. В противном случае, аналогично, его значение в XOR равно 1. Или, проще говоря, одинаковые элементы при суммировании взаимоуничтожатся. |
|
11.04.2024, 01:24 | #3 |
Участник
|
Цитата:
Здесь тоже всё просто: найдем XOR всех чисел — он и будет ответом. В самом деле, если какой-то бит в искомом числе равен нулю, то во всей последовательности он будет равен 1 в чётном числе элементов, и его значение в XOR равно нулю. В противном случае, аналогично, его значение в XOR равно 1. Или, проще говоря, одинаковые элементы при суммировании взаимоуничтожатся. |
|
|
За это сообщение автора поблагодарили: Товарищ ♂uatr (0). |