Максимизируйте побитовое ИЛИ массива, увеличив элементы не более чем на K

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

Учитывая массив arr[] и целое число K , задача состоит в том, чтобы максимизировать побитовое ИЛИ массива arr[] , где каждый элемент arr[] может быть увеличен почти на K .

Примеры:

Input: arr[]= {1, 3, 7, 0, 6, 1}, K = 2
Output: [1 3 8 0 6 1]
Explanation: Increase the number 7 by 1 ie 8 after that or of the array is maximum that is 15

Input: arr[] ={2, 4, 7, 9}, K = 2
Output: [2, 4, 7, 9]
Explanation: The bitwise OR of arr[] is 15 already so no change is required. 15 is the maximum possible OR.  

Подход: Эта проблема может быть решена путем с помощью побитовых операций. Выполните следующие шаги, чтобы решить данную проблему.

  • Найдите побитовое или всех элементов, что бы сказать состояние каждого бита.
  • Начните с MSB (самый значащий бит) , потому что MSB вносит много изменений в окончательное побитовое ИЛИ.
  • Если конкретный бит побитовый или не установлен. Найдите минимальные шаги для установки этого бита.
  • Минимальные шаги для установки i-го бита: (1<<i)-((1<<i)-1) & arr[i] .
  • Подсчитайте минимальные шаги и обновите массив, если минимальные шаги меньше, чем равные K .

Ниже приведена реализация описанного выше подхода.


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

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