Запросы для вычисления побитового ИЛИ массива с обновлениями

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

Дан массив arr[ ] , состоящий из N положительных целых чисел, и двумерный массив Q[][] , состоящий из запросов вида {i, val} , задача для каждого запроса состоит в том, чтобы заменить arr[i] на val и вычислить побитовое значение ИЛИ измененного массива.

Примеры:

Input: arr[ ]= {1, 2, 3}, Q[ ][] = {{1, 4}, {3, 0}}
Output: 7 6
Explanation:
Replacing arr[1] by 4 modifies arr[ ] to {4, 2, 3}. Bitwise OR = 7.
Replacing arr[2] by 0 modifies arr[] to {4, 2, 0}. Bitwise OR = 6.

Input: arr[ ]= {1, 2, 3, 4}, Q[][ ] = {{4, 0}, {2, 8}}
Output: 3 11 
Explanation: 
Replacing arr[3] by 0 modifies arr[ ] to {1, 2, 3, 0}. Bitwise OR = 3.
Replacing arr[2] by 8 modifies arr[] to {1, 8, 3, 0}. Bitwise OR = 11.

Наивный подход: самый простой подход к решению проблемы — пройтись по массиву arr[ ] для каждого i -го запроса после обновления arr[Q[i][0]] на Q[i][1] для вычисления побитового ИЛИ массива .

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

Эффективный подход: выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте массив result[] размером 32. Установите для всех его элементов значение 0.
  • Обходим массив arr[].
    • Перебрать биты каждого элемента массива.
    • Увеличивать результат[j] для каждого j -го неустановленного бита, найденного в текущем элементе массива.

  • Теперь пройдитесь по массиву Q[][] и выполните следующее:
    • Измените результат[] , удалив установленные биты Q[i][0] из соответствующих позиций.
    • Обновите результат[] , добавив установленные биты Q[i][0] из соответствующих позиций.
    • Преобразуйте массив result[] в его эквивалентное десятичное значение и распечатайте его.

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

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

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