Ctrl K

Лучший XOR-партнёр под потолком

Сложная
Дан массив неотрицательных чисел values и список запросов queries, где queries[i] = [x, cap]. Ответ на запрос — наибольшее значение x XOR v среди всех элементов v массива, которые не превосходят cap. Если таких элементов нет (все больше cap), ответ -1. Верните список ответов в порядке запросов.
Пример 1
values=[3, 10, 6, 12], queries=[[5, 7], [9, 2], [1, 20]] → [6, -1, 13]

Для [5, 7] годятся 3 и 6: 5 XOR 3 = 6, 5 XOR 6 = 3, ответ 6. Для [9, 2] все числа больше 2 — ответ -1. Для [1, 20] годятся все, лучшее 1 XOR 12 = 13.

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

С порогом 0 доступен только 0: 8 XOR 0 = 8. С порогом 8: 7 XOR 8 = 15.

Ограничения
  • 1 ≤ len(values), len(queries) ≤ 10⁵
  • 0 ≤ values[j] ≤ 10⁹
  • 0 ≤ x, cap ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСлова для головоломок СложнаяПары с XOR в диапазоне СложнаяЛучший XOR по цепочке начальников СложнаяНаибольший XOR близкой пары СложнаяСамая непохожая пара Средняя
загружаем Python…
Вход
values=[3, 10, 6, 12], queries=[[5, 7], [9, 2], [1, 20]]
Ожидается
[6, -1, 13]

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