Найдите пару чисел с заданным количеством битов, равным не более чем N, и чье побитовое исключающее ИЛИ равно N.

Учитывая положительное целое число N , задача состоит в том, чтобы найти пару целых чисел (X, Y) такую, что побитовое исключающее ИЛИ X и Y равно N , а X * Y максимально, когда количество битов в X и Y меньше или равно Н .

Примеры:

Input: N = 10
Output: 13 7
Explanation: The case where X = 13 and Y = 7 is the most optimal choice as 13 xor 7 = 10 and 13 * 7 = 91 which is maximum possible.

Input: N = 45
Output: 50 31

Подход: Данная проблема может быть решена с использованием следующих наблюдений:

• Если i ^-й бит N равен 0 , то i ^-й бит X и Y должен быть либо 0 , либо 1 . Чтобы максимизировать произведение, установите такие биты как 1 .
• Если i ^-й бит N равен 1 , то один из i ^-х битов X или Y должен быть равен 1 , а другой должен быть равен 0 . Поскольку N должно иметь постоянное количество установленных битов, сумма X и Y должна быть постоянной.
• Если сумма двух чисел постоянна, их произведение максимально, когда разница между двумя числами минимальна.

В соответствии с приведенными выше наблюдениями инициализируйте два целых числа X и Y как 0. Чтобы свести к минимуму разницу между X и Y , X должен быть равен MSB _N , а Y должен быть равен N — MSB _N , где MSB представляет наиболее значимый Кусочек. Кроме того, для всех нулевых битов в N установите соответствующие биты в X и Y как 1 .

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

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