Выбор ответа Junior Биты спрашивают часто обновлено
Единственный без пары
Вопрос
В массиве каждое число встречается дважды, кроме одного. Как найти его за O(n) и O(1) памяти?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: XOR всех элементов: пары взаимно уничтожаются. x ^ x = 0 и x ^ 0 = x, XOR коммутативен.
Варианты ответа
- Отсортировать и сравнить соседние элементы
- Map частот, затем найти ключ с частотой 1
- XOR всех элементов: пары взаимно уничтожаютсяправильный ответ
- Сумма всех минус удвоенная сумма уникальных
Разбор
x ^ x = 0 и x ^ 0 = x, XOR коммутативен. XOR всего массива оставляет только непарное число. O(n), O(1).
- Сортировка O(n log n).
- Map O(n) памяти.
- Формула с суммой уникальных требует Set, то есть O(n) памяти.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.