Самый длинный подмассив, побитовое И каждой пары элементов которого равно 0

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

Примеры:

Input: arr[] = {1, 3, 8, 48, 10}
Output: 3
Explanation: The longest valid subarray is {3, 8, 48}, So, the length of a valid subarray is 3
=> 3 AND 8 = 0.
=> 3 AND 48 = 0.
=> 8 AND 48 = 0.

Input: arr = {3, 1, 5, 11, 13}
Output: 0

Наивный подход:

Generate all the subarray and for each subarray find all the pairs of elements and keep track for any pair has non-zero value, if there is such pair than the current subarray is not valid subarray. If we found any subarray such that the bitwise AND of every pair of elements in the subarray is equal to 0 then maximise the length of this subarray with our result. Finally return the result.

Ниже приведена реализация вышеупомянутой идеи:

• Инициализируйте переменную result = 0 , чтобы отслеживать максимально допустимый подмассив.
• Два вложенных цикла для генерации всего подмассива
  • Сохраняйте переменную flag = true , чтобы отслеживать любой действительный подмассив.
  • Два вложенных цикла для поиска всех пар в диапазоне от i до j
    • Вычислить побитовое И каждой пары
    • Проверить, имеет ли текущая пара ненулевое значение
      • Если правда, сделайте флаг = ложь
  • Проверьте, является ли флаг истинным, это гарантирует, что подмассив в диапазоне от i до j является допустимым подмассивом.
    • Максимизируйте результат с текущей длиной подмассива.
• Вернуть результат .

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

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

Подход с использованием Bit Manipulation:

The bitwise AND of every pair in the subarray should be zero this statement implies that In a valid subarray bits of every element should be unique. 

We’ll use a sliding window approach, tracking used bits. We use bitwise OR to combine bits. If the next number has a conflicting bit (used & arr[i] != 0), shrink the window until there are no conflicts. We’ll use the XOR operation to remove bits during the window shrinks.

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

• Инициализировать переменную, используемую для отслеживания используемого бита.
• Инициализируйте переменную start , чтобы отслеживать начальную позицию скользящего окна.
• Инициализируйте переменный результат , чтобы отслеживать ответ.
• Перебрать заданный массив:
  • Уменьшите окно до ( used & arr[i] != 0 ).
  • Установить биты текущего элемента в используемой переменной.
  • Максимизируйте результат с допустимой длиной подмассива.
• Вернуть результат.

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

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

Статьи по Теме:

• Введение в массив — учебные пособия по структурам данных и алгоритмам
• Введение в побитовые алгоритмы - структуры данных и учебные пособия по алгоритмам
• Техника раздвижения окна