Ctrl K

Поиск кода в двоичной строке

Средняя
Дана строка bits из символов 0 и 1 и список запросов requests, где каждый запрос — пара [key, code]. Для запроса нужно найти непрерывный кусок bits, который, если прочитать его как двоичное число v, удовлетворяет v XOR key == code. Из всех подходящих кусков выберите самый короткий, а среди одинаково коротких — тот, что начинается левее. Ответ на запрос — пара индексов начала и конца куска [left, right] (нумерация с нуля, оба конца включительно) или [-1, -1], если такого куска нет. Верните ответы на все запросы в их исходном порядке.
Пример 1
bits="0110", requests=[[2, 4], [7, 7], [1, 0]] → [[1, 3], [0, 0], [1, 1]]

2 XOR 4 = 6, это «110» — отрезок [1, 3]. 7 XOR 7 = 0, это «0» — отрезок [0, 0]. 1 XOR 0 = 1, первая единица стоит на позиции 1 — отрезок [1, 1].

Пример 2
bits="111", requests=[[3, 1], [0, 8]] → [[-1, -1], [-1, -1]]

3 XOR 1 = 2, это «10», но нуля в строке нет. 0 XOR 8 = 8, это «1000» — тоже не найти. Оба ответа [-1, -1].

Ограничения
  • 1 ≤ len(bits) ≤ 10⁴
  • Каждый символ bits — 0 или 1
  • 1 ≤ len(requests) ≤ 10⁵
  • 0 ≤ key, code ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПалиндром после пары правок СредняяПлюс одна буква СредняяСлова для головоломок СложнаяСлова с рабочих клавиш ЛёгкаяИмена с обменом первых букв Сложная
загружаем Python…
Вход
bits="0110", requests=[[2, 4], [7, 7], [1, 0]]
Ожидается
[[1, 3], [0, 0], [1, 1]]

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