Минимальные удаления в диапазоне, чтобы сделать побитовое И ненулевым для заданных запросов диапазона

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

Учитывая массив запросов [][] из Q запросов диапазона, задача состоит в том, чтобы найти минимальные удаления из диапазона [l, r] , чтобы побитовое И диапазона было ненулевым значением.

Примеры:

Input: queries[][] = { {1, 5}, {3, 4}, {5, 10}, {10, 15}}
Output: 2 1 3 0 
Explanation: 
Query-1: l = 1, r = 5 {1, 2, 3, 4, 5} (2, 4 ) should be removed to make the AND of the array non-zero so minimum removals is 2.
Query-2: l = 3, r = 4 {3, 4} Either 3 or 4 should be removed to make the AND of the array non-zero so minimum removals is 1.
Query-3: l = 5, r = 10 {5, 6, 7, 8, 9, 10} (5, 6, 7) or (8, 9, 10) should be removed to make the AND of range non-zero. Minimum removals 3.
Query-4: l = 10, r = 15 {10, 11, 12, 13, 14, 15} the AND of the array is non-zero initially so 0 removals.

Input:  queries[][] = { {100, 115}, {30, 40}, {101, 190} };
Output: 0 2 27 

Наивный подход: это можно решить, перебирая каждый диапазон и проверяя максимальное количество элементов в диапазоне, имеющем общий установленный бит, и удаляя его из общего количества элементов, т.е. (r – l + 1) .

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

Временная сложность: O (31 * Q * n ), где n — длина максимального диапазона.
Вспомогательное пространство: O(1)

Эффективный подход: этот подход основан на динамическом программировании и технике суммирования префиксов. Это можно сделать, сохранив общее количество установленных битов до этого диапазона в массиве с использованием dp[] в каждой позиции из 31 бита. Здесь состояние dp[i][j] означает, что общее количество установленных битов позиции j-го бита до i из [1, i] . Выполните следующие действия, чтобы решить вышеуказанную проблему:

  • Вызовите функцию count_set_bits() для предварительного расчета массива dp[][] с использованием префикса sum .
  • Теперь выполните итерацию по запросам и назначьте l = q[i][0], r = q[i][1] .
    • Инициализируйте max_set = INT_MIN , чтобы сохранить подсчет максимального количества элементов в диапазоне с установленным j-м битом.
    • Перебрать биты из [0, 30] .
    • Подсчитайте количество элементов с j-м битом, установленным total_set = (dp[r][j] – dp[l – 1][j]) .
    • Сохраните максимальное количество элементов с установленным j-м битом, взяв max(max_set, total_set) .
  • Выведите минимальные требуемые удаления, вычитая max_set из общей длины (r-l+1) .

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

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

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