Найдите максимальное значение AND среди всех подмножеств размера K данного массива

Учитывая массив arr[] , содержащий N неотрицательных целых чисел, задача состоит в том, чтобы найти максимальное значение AND среди всех подмножеств, имеющих длину K .

Примеры:

Input: arr[] = {1, 6, 9, 7}, K = 1
Output: 9
Explanation: As only one element is allowed 9 is the greatest value that can be obtained.

Input: arr[] = {3, 3, 3}, K = 2
Output: 3

Input: arr[] = {7, 8, 9, 10, 11, 12}, K = 3
Output: 8

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

Сложность времени: О(2 ^Н. Н)
Вспомогательное пространство: O(N)

Эффективное решение: вклад бита в любой позиции больше, чем совокупный вклад всех битов справа от него. Это означает, что значение битов имеет значение слева направо (от MSB до LSB). Так что жадно попытайтесь сначала установить крайние левые биты и проверьте числа, которые помогут в этом. Выполните следующие шаги, чтобы найти подмножество длины K , имеющее максимальное значение AND:

1. Рассмотрите возможность инициализации этого оптимального набора со всеми значениями в массиве.
2. Перебрать все позиции битов, начиная с i = 30 до 0.
3. Проверьте, есть ли более K чисел, имеющих установленный бит в i-й позиции.
4. Если есть, обновите оптимальный набор этим новым набором значений (который является не чем иным, как подмножеством оптимального набора)
5. Если на какой-либо итерации размер подмножества становится точно K , разбить и вернуть этот набор.

Note: It is also possible that there are more than K values in our set after all the iterations This will simply mean that there are some repeating numbers in set (So they will not affect the answer). 
Here is one example that can be considered :
arr[] = {3, 3, 3 }, K = 2
ans = 3 & 3 = 3  (if this optimal set is printed using the below code the answer will be [3, 3, 3] which will not  affect the maximum and of the subset)

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

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