Максимизируйте исключающее ИЛИ, выбрав 3 числа в диапазоне [0, A], [0, B] и [0, C] соответственно.

Опубликовано: 21 Сентября, 2022

Учитывая 3 целых числа A , B , C , задача состоит в том, чтобы найти максимальное значение XOR для трех чисел, выбранных по одному из каждого диапазона [0, A], [0, B], [0, C] соответственно.

Пример:

Input: A = 1, B = 2, C = 4
Output: 7
Explanation: Maximum XOR can be calculated by selecting 1 (from [0, 1]), 2 (from [0, 2]) & 4 (from [0, 4]) i.e. 1⊕ 2⊕ 4 = 7

Input: A = 6, B = 2, C = 10
Output: 15
Explanation: Maximum XOR can be calculated by selecting 5 (from [0, 6]), 1 (from [0, 2]) & 10 (from [0, 10]) i.e. 5⊕ 1⊕ 10 = 15.

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

Временная сложность: O(A*B*C)

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

Эффективный подход:

Чтобы найти наибольшее значение операции XOR, значение XOR должно иметь каждый бит, чтобы быть установленным битом, т. е. в 32-битном числе цель состоит в том, чтобы получить наибольшее 1 множество, начиная слева направо. Это можно сделать, выполнив следующие шаги:

  1. Создайте переменную ans , в которой будет храниться значение максимально возможного xor, и инициализируйте его нулем.
  2. Чтобы создать 32-битное значение, которое было бы максимально возможным xor, запустите цикл для каждого из его битов от самого старшего бита до самого младшего бита.
  3. Теперь для каждого бита:
    • Создайте переменную cur , в которой будет храниться минимальное число, в котором установлен этот бит.
    • Проверьте каждый диапазон A, B, C и попытайтесь найти число с установленным битом в этой позиции. Это можно сделать, сравнив A, B и C с cur, т.е. если какое-либо число из A, B и C больше или равно cur, то оно будет содержать установленный бит в этой позиции. Если установленный бит найден в любом из чисел от A, B, C, тогда максимальный xor также будет содержать установленный бит в этой позиции.
    • Теперь, если найден установленный бит, добавьте cur к ans, чтобы установить в нем этот бит, и уменьшите значение числа, в котором найден установленный бит (от A, B, C), на cur, чтобы сбросить этот бит как его нельзя использовать повторно.
    • Выполните вышеуказанные шаги для каждого бита, чтобы вычислить окончательное значение ответа.
  4. После вышеперечисленных шагов распечатайте требуемый результат.

Реализация:

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ