MEX сгенерированной последовательности из N+1 целых чисел, где i-е целое представляет собой операцию XOR (i-1) и K

Для заданных двух целых чисел N и K сгенерируйте последовательность размера N+1 , где i ^-й элемент равен (i-1)⊕K , задача состоит в том, чтобы найти MEX этой последовательности. Здесь MEX последовательности — это наименьшее неотрицательное целое число, которое не встречается в последовательности.

Примеры:

Input: N = 7, K=3
Output: 8
Explanation: Sequence formed by given N and K is {0⊕3, 1⊕3, 2⊕3, 3⊕3, 4⊕3, 5⊕3, 6⊕3, 7⊕3} i.e {3, 2, 1, 0, 7, 6, 5, 4}
Smallest non-negative number not present in the given sequence is 8

Input: N = 6, K=4
Output: 3

Родной подход: Самый простой подход к решению этой проблемы — просто создать массив данных и вычислить его MEX . Ниже приведены шаги для решения этой проблемы:

1. Создайте последовательность и отсортируйте ее.
2. Инициализируйте MEX равным 0 и выполните итерацию по отсортированному массиву, если текущий элемент равен MEX , увеличьте MEX на 1, в противном случае цикл прервется.
3. В качестве ответа на эту задачу выведите MEX .

Ниже приведена реализация вышеуказанного подхода:

Сложность времени: О (N * журнал (N))
Вспомогательное пространство: НА)

Эффективный подход: если в этой последовательности встречается число M , то для некоторого i ^-го члена (i-1)⊕K = M , что также означает M⊕K = (i-1) , где максимальное значение ( i-1 ) это Н. Теперь предположим, что X — это MEX данной последовательности, тогда X⊕K должно быть больше, чем N , т. е . X⊕K > N. Таким образом, минимальное значение X — это MEX последовательности. Выполните следующие шаги, чтобы решить эту проблему:

1. Перебрать биты как N+1 , так и K в обратном порядке.
2. Если i ^-й бит K равен i ^-му биту N+1, установить i ^-й бит X равным 0.
3. Если i ^-й бит K равен 0 , а i ^-й бит N+1 равен 1, установите i ^-й бит X в 1.
4. Если i ^-й бит K равен 1 , а i ^-й бит N+1 равен 0 , установите все остальные младшие биты X в 0, потому что это означает, что число, содержащее установленный бит в этой позиции, равно отсутствует, и это MEX последовательности.
5. Выведите ответ в соответствии с приведенным выше наблюдением.

Ниже приведена реализация вышеуказанного подхода:

Сложность времени: О (журнал (макс (N, К))
Вспомогательное пространство: О(1)