Побитовое ИЛИ побитового И всех подмассивов массива

Учитывая массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы найти побитовое ИЛИ побитового И всех подмассивов данных массивов.

Примеры:

Input: arr[] = {1, 2, 3}
Output: 3
Explanation:
The following are Bitwise AND of all possible subarrays are:

1. {1}, Bitwise AND is 1.
2. {1, 2}, Bitwise AND is 0.
3. {1, 2, 3}, Bitwise AND is 0.
4. {2}, Bitwise AND is 2.
5. {2, 3}, Bitwise AND is 2.
6. {3}, Bitwise AND is 3.

The Bitwise OR of all the above values is 3.

Input: arr[] = {1, 4, 2, 10}
Output: 15

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

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать, основываясь на наблюдении, что побитовое И любого подмассива всегда меньше или равно первому элементу в подмассиве. Следовательно, максимально возможное значение — это побитовое И подмассивов сами элементы. Поэтому задача сводится к нахождению в результате побитового ИЛИ всех элементов массива.

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

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