Минимальные удаления в диапазоне, чтобы сделать побитовое И ненулевым для заданных запросов диапазона
Учитывая массив запросов [][] из 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)