Максимальное ИЛИ двух чисел в массиве

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

Пример:

Input: Arr = {25, 10, 2, 8, 5, 3}
Output: 29

Input: Arr = {1, 2, 3, 4, 5, 6, 7}
Output: 7

Наивный подход: простое решение состоит в том, чтобы сгенерировать все пары заданного массива и вычислить ИЛИ пар. Наконец, верните максимальное значение XOR.

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

Лучший подход: подход основан на следующем побитовом наблюдении:

• Если мы установим все биты текущего arr[i], т.е. скажем, arr[i]=10 (1010),
• и меняем на 15 (1111),
• и текущее максимальное OR, рассчитанное на данный момент, больше 15,
• тогда нам не нужно проверять arr[i], так как это не повлияет на наш ответ.

Это кажется небольшим изменением, но оно значительно сократит время.

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

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