Ctrl K

Самая непохожая пара

Средняя
Дан массив неотрицательных целых чисел values. Выберите два элемента (можно взять один и тот же элемент дважды) так, чтобы их побитовый XOR был как можно больше, и верните это значение. Перебор всех пар работает за O(n²) — попробуйте быстрее.
Пример 1
values=[6, 9, 4, 12] → 15

6 = 0110 и 9 = 1001 различаются во всех четырёх битах: 6 XOR 9 = 15.

Пример 2
values=[7, 7] → 0

Числа одинаковые, их XOR равен 0.

Пример 3
values=[16, 3, 20, 2] → 23

Лучше всего 3 XOR 20 = 23; для сравнения, 2 XOR 20 = 22, а 16 XOR 3 = 19.

Ограничения
  • 1 ≤ len(values) ≤ 2·10⁵
  • 0 ≤ values[i] ≤ 2³¹ − 1
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСлова для головоломок СложнаяЛучший XOR по цепочке начальников СложнаяXOR близкой пары ЛёгкаяНаибольший XOR близкой пары СложнаяРазбиение на слова из словаря Средняя
загружаем Python…
Вход
values=[6, 9, 4, 12]
Ожидается
15

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 99 тестов на сервере, включая скрытые.