Проверьте, существует ли пара целых чисел из двух диапазонов, такая, что их побитовое XOR превышает оба диапазона
Для заданных двух целых чисел A и B задача состоит в том, чтобы проверить, существуют ли два целых числа P и Q в диапазоне [1, A] и [1, B] соответственно, такие, что побитовое XOR для P и Q больше, чем A и B . Если найдено верно, то выведите «Да» . В противном случае выведите «Нет» .
Примеры:
Input: X = 2, Y = 2
Output: Yes
Explanation:
By choosing the value of P and Q as 1 and 2 respectively, gives the Bitwise XOR of P and Q as 1^2 = 3 which is greater than Bitwise XOR of A and B A ^ B = 0.
Therefore, print Yes.Input: X = 2, Y = 4
Output: No
Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные пары ( P, Q ) , пройдя все целые числа от 1 до X и от 1 до Y , и проверить, существует ли пара такая, что их побитовое исключающее ИЛИ больше, чем Побитовое исключающее ИЛИ X и Y , затем выведите «Да» . В противном случае выведите «Нет» .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(X * Y)
Вспомогательное пространство: O(1)
Эффективный подход. Описанный выше подход также можно оптимизировать на основе следующих наблюдений:
- Для любых двух целых чисел P и Q максимальное значение побитового исключающего ИЛИ равно (P + Q) , которое можно найти только в том случае, если между P и Q в их двоичном представлении нет общих битов.
- Есть два случая:
- Случай 1: Если у игрока А есть два целых числа, которые дают максимальное значение побитового исключающего ИЛИ, выведите «Нет» .
- Случай 2: В этом случае между A и B должен быть какой-то общий бит, такой, что всегда существуют два целых числа P и Q , чье побитовое исключающее ИЛИ всегда больше, чем побитовое исключающее ИЛИ A и B , где (P ^ Q) = ( Х|У) .
Следовательно, из приведенных выше наблюдений идея состоит в том, чтобы проверить, равно ли значение данного A ^ B A + B или нет. Если найдено верно, то выведите «Нет» . В противном случае выведите «Да» .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(1)
Вспомогательное пространство: O(1)