Разделить массив на максимальное количество подмножеств с одинаковым побитовым И

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

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

Примеры:

Input: N = 4, arr[] = {1, 5, 2, 8}
Output: 2
Explanation:
1st subset -> {1, 8}; bitwise AND = 0 
2nd subset -> {2, 5}; bitwise AND = 0 

Input: N = 3, arr[] = {1, 5, 7}
Output: 1
Explanation: There is no way to split the array into subsets. So all the elements can be considered as a single subset.

Input: N = 5, arr[] = {7, 14, 6, 15, 22}
Output: 3
Explanation: The subsets are {22, 15}, {6} and {7, 14}

Подход: грубая сила

Say all the subsets have an equal AND and that is denoted by the variable target. We can find this target value by taking AND of all the elements in the array. This can be proved as follows:

Let’s say the subsets are S1, S2, . . ., Sk, and the bitwise AND of each subset is X. So, S1 & S2 & . . . & Sk = target. As all the elements are part of any one subset, so the bitwise AND of all the elements is also a target.

So the task is to find all the possible combinations of elements to find a maximum number of subsets that can be formed.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Мы можем сохранить маску, которая представляет элементы, взятые до сих пор.
  • Если текущий элемент отсутствует в маске И он с маской и есть 2 варианта для элемента:
    • Если после добавления элемента И подмножества не равно целевому , добавьте этот элемент в текущее подмножество.
    • Если после добавления силы элемента И подмножества равно целевому , то может быть два возможных пути:
      • Добавьте этот элемент в текущее подмножество и начните добавлять элементы в новое подмножество.
      • Продолжайте добавлять новые элементы в текущее подмножество.
  • После добавления текущего элемента вызовите функцию добавления новых элементов и уменьшите значение n на 1.
  • Когда n становится равным нулю, проверьте, все ли подмножества имеют И, равные цели , а затем обновите ответ.
  • Проверьте, все ли пары имеют одинаковое И, поддерживая текущую переменную, которая представляет текущее И элементов, добавленных в новое подмножество.
    • Если в текущем заданы все биты, это означает, что мы нашли пару с И = цель [Поскольку n будет равно 0, когда все элементы используются, и при вызове новой группы переданное начальное значение И совпадает с сохраненным значением по умолчанию. в начале].
    • В противном случае текущее подмножество И не равно И.

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

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

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