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

Опубликовано: 25 Февраля, 2023

Дан массив arr[] длины N . Вы можете выполнить не более K операций над массивом следующего типа:

  • Выберите индекс i (0 ≤ i ≤ N-1) и установите j -й бит arr[i] равным 1 (0 ≤ j ≤ 30).

Задача состоит в том, чтобы найти максимально возможное значение побитового И всех элементов массива после выполнения не более чем K операций.

Примеры:

Input: N = 3, K = 2, Arr = [1, 2, 3]
Output: 3
Explanation: Following is the 32 bit binary representation of 1, 2, 3.
1->00000000000000000000000000000001
2->00000000000000000000000000000010
3->00000000000000000000000000000011
So, set 0th bit of 2 and 1st bit of 1 which will require 2 operation. 
Now the binary representation of the numbers will be
3->00000000000000000000000000000011
3->00000000000000000000000000000011
3->00000000000000000000000000000011
So, 3 & 3 & 3 = 3 .

Input: N = 7, K = 0, Arr = [4, 6, 6, 28, 6, 6, 12]
Output: 4
Explanation: Since K is 0 we cannot do any operation. 
So the bitwise AND of the array is (4 & 6 & 6 & 28 & 6 & 6 & 12) = 4 . 

Подход: Задача может быть решена на основе следующей идеи:

The bitwise AND will be larger when all the bits (as left as possible )of all the elements are set. So, set the most significant bit that is possible in all the elements of the array

Выполните следующие шаги, чтобы решить проблему:

  • Объявите вектор bits_Count , который будет хранить общее количество установленных битов в j -м бите (0 ≤ j ≤ 30) всех чисел массива.
  • Теперь пройдите по bits_Count в обратном порядке и проверьте, является ли K ≥ N – bits_Count[i] (0 ≤ i ≤ N-1)
    • Если условие выполнено, уменьшите K на N – bits_Count[i] и установите bits_Count[i] = N .
  • Объявите переменную max_Ans и инициализируйте ее значением 0.
  • Теперь пройдитесь по массиву bits_Count от i = 0 до 30:
    • Проверьте, если bits_Count[i] = N , затем увеличьте max_Ans на 2 i (0 ≤ i ≤ 30).
  • Верните max_Ans в качестве требуемого ответа.

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

Временная сложность: O(N * 32)
Вспомогательное пространство: O (1), потому что используется только дополнительный массив размером 32, который является постоянным.

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