Наименьшая пара целых чисел с минимальной разницей, чье побитовое исключающее ИЛИ равно N

Для заданного положительного целого числа N задача состоит в том, чтобы найти два наименьших целых числа A и B , для которых побитовое исключающее ИЛИ для A и B равно N , а разница между A и B минимальна.

Примеры:

Input: N = 26
Output: 10 16
Explanation:
The Bitwise XOR of 10 and 16 is 26 and the difference between them is minimum.

Input: N = 1
Output: 0 1

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные пары чисел в диапазоне [0, N] и вывести ту пару чисел, чье побитовое исключающее ИЛИ является заданным числом N , и оба числа являются наименьшими.

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

Эффективный подход. Описанный выше подход также можно оптимизировать на основе следующих наблюдений:

• Рассмотрим двоичное представление любого числа «1100011» , тогда число может быть разделено вокруг их старшего бита (MSB) как «1000000» и «100011» , а побитовое XOR этих чисел является заданным числом.
• Из приведенного выше разделения можно заметить, что число, образованное «1000000» (скажем, A ) и «100011» (скажем, B ), минимально, и их разница между ними минимальна, поскольку значение, образованное B , всегда меньше и ближе всего. к А .

Из приведенных выше наблюдений минимальное значение A и B , удовлетворяющее заданным критериям, состоит в том, чтобы разделить заданное число N вокруг его самого старшего бита (MSB) .

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

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