Минимальное исключающее ИЛИ не более чем K элементов в диапазоне [L, R]

Учитывая три целых числа L , R и K , задача состоит в том, чтобы найти минимальное побитовое исключающее ИЛИ не более чем K целых чисел между [L, R] .

Примеры:

Input: L = 1, R = 10, K = 3
Output: 0
Explanation:
Choose elements 4, 5, and 1 in the range [1, 10] and the Bitwise XOR of the chosen elements is 0, which is minimum. 

Input: L = 32, R = 33, K = 2
Output: 1
Explanation:
Choose elements 32, and 33 in the range [32, 33] and the Bitwise XOR of the chosen elements is 1, which is minimum.

Подход: наблюдение, которое помогает нам в решении проблемы, — это побитовое исключающее ИЛИ двух чисел X и (X+1) равно 1 , если X — четное число. Таким образом, побитовое исключающее ИЛИ четырех последовательных чисел будет равно 0 , если первое из них четное.

Выполните следующие шаги, чтобы решить проблему:

• Если значение K больше 4 , то ответ всегда равен 0. (Это связано с тем, что четыре числа X, (X+1), (X+2) и (X+3) всегда можно найти в диапазоне 5 , где X — четное число.)
• Если значение K равно 2 , вызовите функцию func2() , которая принимает L, R , и K в качестве входных параметров и выполняет следующие действия:
  • Если значение (RL) больше или равно 2 , т. е. в диапазоне есть как минимум 3 числа, вернуть 1 (это связано с тем, что два числа X и X+1 всегда можно найти в диапазоне 3 , где X четное число.)
  • В противном случае вернуть минимум L и (L^R).
• Если значение K равно 3 , вызовите функцию func3() , которая принимает L, R , и K в качестве входных параметров и выполняет следующие действия:
  • Если (R^L) лежит между L и R , вернуть 0 . (Это потому, что (R ^ L) ^ L ^ R = 0) )
  • В противном случае вернуть func2(L, R, K)
• Если значение K равно 4 , вызовите функцию func4() , которая принимает L, R , и K в качестве входных параметров и выполняет следующие действия:
  • Если (RL) больше или равно 4 , т. е. в диапазоне есть не менее 5 чисел, вернуть 0. (Это связано с тем, что четыре числа X, (X+1), (X+2) и (X+ 3) всегда можно найти в диапазоне от 5 , где X — четное число.)
  • В противном случае вернуть минимум Xor из четырех чисел в диапазоне [L, R] и func3(L, R, K) .
• В противном случае вернуть Л.

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

Временная сложность: O(1)
Вспомогательное пространство: O(1)