Dada una consulta de array [][] de consultas de rango Q , la tarea es encontrar las eliminaciones mínimas del rango [l, r] de modo que el AND bit a bit del rango sea un valor distinto de cero.
Ejemplos:
Entrada: consultas[][] = { {1, 5}, {3, 4}, {5, 10}, {10, 15}}
Salida: 2 1 3 0
Explicación:
Consulta-1: l = 1, r = 5 {1, 2, 3, 4, 5} (2, 4 ) debe eliminarse para que el AND de la array no sea cero, de modo que las eliminaciones mínimas sean 2.
Consulta-2: l = 3, r = 4 {3 , 4} Se debe eliminar 3 o 4 para que el AND de la array no sea cero, de modo que las eliminaciones mínimas sean 1.
Consulta-3: l = 5, r = 10 {5, 6, 7, 8, 9, 10} (5, 6, 7) o (8, 9, 10) deben eliminarse para que el AND del rango no sea cero. Eliminaciones mínimas 3.
Consulta-4: l = 10, r = 15 {10, 11, 12, 13, 14, 15} el AND de la array es inicialmente distinto de cero, por lo que 0 eliminaciones.Entrada: consultas[][] = { {100, 115}, {30, 40}, {101, 190} };
Salida: 0 2 27
Enfoque ingenuo: esto se puede resolver iterando a través de cada rango y verificando el recuento máximo de elementos en el rango que tiene el bit establecido común y eliminándolo del recuento total de elementos, es decir (r – l + 1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function the find the minimum removals
// to make the bitwise AND of range non-zero
void solve_queries(vector<vector<int> > q)
{
for (int i = 0; i < q.size(); i++) {
int l = q[i][0];
int r = q[i][1];
// Initialize the max_set to check
// what count of set bit majority of
// numbers in the range was set
int max_set = 0;
for (int i = 0; i < 31; i++) {
int cnt = 0;
for (int j = l; j <= r; j++) {
// Check if is set
if ((1 << i) & j) {
cnt++;
}
}
max_set = max(max_set, cnt);
}
// Total length of range - count of
// max numbers having 1 bit set in range
cout << (r - l + 1) - max_set << " ";
}
}
// Driver Code
int main()
{
// Initialize the queries
vector<vector<int> > queries
= { { 1, 5 }, { 3, 4 }, { 5, 10 }, { 10, 15 } };
solve_queries(queries);
return 0;
}
Java
// Java code to implement the above approach
import java.util.*;
public class GFG
{
// Function the find the minimum removals
// to make the bitwise AND of range non-zero
static void solve_queries(int [][]q)
{
for (int i = 0; i < q.length; i++) {
int l = q[i][0];
int r = q[i][1];
// Initialize the max_set to check
// what count of set bit majority of
// numbers in the range was set
int max_set = 0;
for (int k = 0; k < 31; k++) {
int cnt = 0;
for (int j = l; j <= r; j++) {
// Check if is set
if (((1 << k) & j) != 0) {
cnt++;
}
}
max_set = Math. max(max_set, cnt);
}
// Total length of range - count of
// max numbers having 1 bit set in range
System.out.print((r - l + 1) - max_set + " ");
}
}
// Driver code
public static void main(String args[])
{
// Initialize the queries
int [][]queries
= { { 1, 5 }, { 3, 4 }, { 5, 10 }, { 10, 15 } };
solve_queries(queries);
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python program for the above approach
# Function the find the minimum removals
# to make the bitwise AND of range non-zero
def solve_queries (q):
for i in range(len(q)):
l = q[i][0]
r = q[i][1]
# Initialize the max_set to check
# what count of set bit majority of
# numbers in the range was set
max_set = 0
for i in range(31):
cnt = 0
for j in range(l, r + 1):
# Check if is set
if ((1 << i) & j):
cnt += 1
max_set = max(max_set, cnt)
# Total length of range - count of
# max numbers having 1 bit set in range
print(f"{(r - l + 1) - max_set} ", end=" ")
# Driver Code
# Initialize the queries
queries = [[1, 5], [3, 4], [5, 10], [10, 15]]
solve_queries(queries)
# This code is contributed by gfgking
C#
// C# code to implement the above approach
using System;
public class GFG{
// Function the find the minimum removals
// to make the bitwise AND of range non-zero
static void solve_queries(int[,] q)
{
for (int i = 0; i < 4; i++) {
int l = q[i, 0];
int r = q[i, 1];
// Initialize the max_set to check
// what count of set bit majority of
// numbers in the range was set
int max_set = 0;
for (int k = 0; k < 31; k++) {
int cnt = 0;
for (int j = l; j <= r; j++) {
// Check if is set
if (((1 << k) & j) != 0) {
cnt++;
}
}
max_set = Math.Max(max_set, cnt);
}
// Total length of range - count of
// max numbers having 1 bit set in range
Console.Write((r - l + 1) - max_set + " ");
}
}
// Driver code
static public void Main()
{
// Initialize the queries
int[,] queries = new int[4,2] { { 1, 5 }, { 3, 4 }, { 5, 10 }, { 10, 15 } };
solve_queries(queries);
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
// JavaScript program for the above approach
// Function the find the minimum removals
// to make the bitwise AND of range non-zero
const solve_queries = (q) => {
for(let i = 0; i < q.length; i++)
{
let l = q[i][0];
let r = q[i][1];
// Initialize the max_set to check
// what count of set bit majority of
// numbers in the range was set
let max_set = 0;
for(let i = 0; i < 31; i++)
{
let cnt = 0;
for(let j = l; j <= r; j++)
{
// Check if is set
if ((1 << i) & j)
{
cnt++;
}
}
max_set = Math.max(max_set, cnt);
}
// Total length of range - count of
// max numbers having 1 bit set in range
document.write(`${(r - l + 1) - max_set} `);
}
}
// Driver Code
// Initialize the queries
let queries = [ [ 1, 5 ], [ 3, 4 ],
[ 5, 10 ], [ 10, 15 ] ];
solve_queries(queries);
// This code is contributed by rakeshsahni
</script>
Producción
2 1 3 0
Complejidad de tiempo: O (31 * Q * n ) donde n es la longitud del rango máximo.
Espacio Auxiliar: O(1)
Enfoque eficiente: este enfoque se basa en la programación dinámica y la técnica de suma de prefijos . Esto se puede hacer almacenando el recuento de bits establecidos totales hasta ese rango en una array usando dp[] en cada posición de 31 bits. Aquí, el estado de dp[i][j] significa que el conjunto total de bits de la j-ésima posición de bit hasta i de [1, i] . Siga estos pasos para resolver el problema anterior:
- Realice una llamada de función a count_set_bits() para precalcular la array dp[][] usando el prefijo sum .
- Ahora repita las consultas y asigne l = q[i][0], r = q[i][1] .
- Inicialice max_set = INT_MIN para almacenar el recuento del recuento máximo de elementos en el rango que tiene el j-ésimo bit establecido.
- Iterar a través de los bits de [0, 30] .
- Cuente el número de elementos que tienen j-ésimo bit establecido por total_set = (dp[r][j] – dp[l – 1][j]) .
- Almacene el recuento máximo de elementos que tienen el j-ésimo bit establecido tomando max(max_set, total_set) .
- Imprima las eliminaciones mínimas requeridas restando max_set de la longitud total (r-l+1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int dp[200005][31];
// Function to build the dp array
// which stores the set bits for
// each bit position till 200005.
void count_set_bits()
{
int N = 2e5 + 5;
for (int i = 1; i < N; i++) {
for (int j = 0; j <= 30; j++) {
// If j th bit is set assign
// dp[i][j] =1 where dp[i][j] means
// number of jth bits set till i
if (i & (1 << j))
dp[i][j] = 1;
// Calculate the prefix sum
dp[i][j] += dp[i - 1][j];
}
}
}
// Function to solve the queries
void solve_queries(vector<vector<int> > q)
{
// Call the function to
// precalculate the dp array
count_set_bits();
for (int i = 0; i < q.size(); i++) {
int l = q[i][0];
int r = q[i][1];
// Initialize the max_set = INT_MIN to
// check what count of set bit
// majority of numbers in the range was set
int max_set = INT_MIN;
// For each bit check the
// maximum numbers in the range
// having the jth bit set
for (int j = 0; j <= 30; j++) {
int total_set = (dp[r][j] - dp[l - 1][j]);
max_set = max(max_set, total_set);
}
// Total length of range - count of max
// numbers having 1 bit set in the range
cout << (r - l + 1) - max_set << " ";
}
}
// Driver Code
int main()
{
// Initialize the queries
vector<vector<int> > queries
= { { 1, 5 }, { 3, 4 }, { 5, 10 }, { 10, 15 } };
solve_queries(queries);
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
class GFG
{
public static int dp[][] = new int[200005][31];
// Function to build the dp array
// which stores the set bits for
// each bit position till 200005.
public static void count_set_bits()
{
int N = 200005;
for (int i = 1; i < N; i++)
{
for (int j = 0; j <= 30; j++)
{
// If j th bit is set assign
// dp[i][j] =1 where dp[i][j] means
// number of jth bits set till i
if ((i & (1 << j))!=0)
dp[i][j] = 1;
// Calculate the prefix sum
dp[i][j] += dp[i - 1][j];
}
}
}
// Function to solve the queries
public static void solve_queries(int[][] q)
{
// Call the function to
// precalculate the dp array
count_set_bits();
for (int i = 0; i < q.length; i++) {
int l = q[i][0];
int r = q[i][1];
// Initialize the max_set = INT_MIN to
// check what count of set bit
// majority of numbers in the range was set
int max_set = Integer.MIN_VALUE;
// For each bit check the
// maximum numbers in the range
// having the jth bit set
for (int j = 0; j <= 30; j++) {
int total_set = (dp[r][j] - dp[l - 1][j]);
max_set = Math.max(max_set, total_set);
}
// Total length of range - count of max
// numbers having 1 bit set in the range
System.out.print((r - l + 1) - max_set + " ");
}
}
// Driver Code
public static void main (String[] args)
{
// Initialize the queries
int[][] queries = new int[][]
{
new int[] { 1, 5 },
new int[] { 3, 4 },
new int[] { 5, 10 },
new int[] { 10, 15 }
};
solve_queries(queries);
}
}
// This code is contributed by Shubham Singh
Python3
# Python program for the above approach dp = [[0 for i in range(31)] for j in range(200005)] # Function to build the dp array # which stores the set bits for # each bit position till 200005. def count_set_bits(): N = 200005 for i in range(1, N): for j in range(31): # If j th bit is set assign # dp[i][j] =1 where dp[i][j] means # number of jth bits set till i if (i & (1 << j)): dp[i][j] = 1 # Calculate the prefix sum dp[i][j] += dp[i - 1][j] # Function to solve the queries def solve_queries(q): # Call the function to # precalculate the dp array count_set_bits() for i in range(len(q)): l = q[i][0] r = q[i][1] # Initialize the max_set = INT_MIN to # check what count of set bit # majority of numbers in the range was set max_set = -2**32 # For each bit check the # maximum numbers in the range # having the jth bit set for j in range(31): total_set = (dp[r][j] - dp[l - 1][j]) max_set = max(max_set, total_set) # Total length of range - count of max # numbers having 1 bit set in the range print((r - l + 1) - max_set, end=" ") # Driver Code # Initialize the queries queries = [[1, 5], [3, 4], [5, 10], [10, 15]] solve_queries(queries) # This code is contributed by Shubham Singh
C#
// C# code to implement the above approach
using System;
public class GFG{
public static int[,] dp = new int[200005,31];
// Function to build the dp array
// which stores the set bits for
// each bit position till 200005.
public static void count_set_bits()
{
int N = 200005;
for (int i = 1; i < N; i++)
{
for (int j = 0; j <= 30; j++)
{
// If j th bit is set assign
// dp[i,j] =1 where dp[i,j] means
// number of jth bits set till i
if ((i & (1 << j))!=0)
dp[i,j] = 1;
// Calculate the prefix sum
dp[i,j] += dp[i - 1,j];
}
}
}
// Function to solve the queries
public static void solve_queries(int[][] q)
{
// Call the function to
// precalculate the dp array
count_set_bits();
for (int i = 0; i < q.Length; i++) {
int l = q[i][0];
int r = q[i][1];
// Initialize the max_set = INT_MIN to
// check what count of set bit
// majority of numbers in the range was set
int max_set = Int32.MinValue;
// For each bit check the
// maximum numbers in the range
// having the jth bit set
for (int j = 0; j <= 30; j++) {
int total_set = (dp[r,j] - dp[l - 1,j]);
max_set = Math.Max(max_set, total_set);
}
// Total length of range - count of max
// numbers having 1 bit set in the range
Console.Write((r - l + 1) - max_set + " ");
}
}
// Driver Code
static public void Main ()
{
// Initialize the queries
int[][] queries = new int[][]
{
new int[] { 1, 5 },
new int[] { 3, 4 },
new int[] { 5, 10 },
new int[] { 10, 15 }
};
solve_queries(queries);
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
// JavaScript program for the above approach
let dp = new Array(200005)
for(let i = 0; i < 200005; i++){
dp[i] = new Array(31).fill(0)
}
// Function to build the dp array
// which stores the set bits for
// each bit position till 200005.
function count_set_bits(){
let N = 200005
for(let i = 1; i < N; i++){
for(let j = 0; j < 31; j++){
// If j th bit is set assign
// dp[i][j] =1 where dp[i][j] means
// number of jth bits set till i
if (i & (1 << j))
dp[i][j] = 1
// Calculate the prefix sum
dp[i][j] += dp[i - 1][j]
}
}
}
// Function to solve the queries
function solve_queries(q){
// Call the function to
// precalculate the dp array
count_set_bits()
for(let i = 0; i < q.length; i++){
let l = q[i][0]
let r = q[i][1]
// Initialize the max_set = INT_MIN to
// check what count of set bit
// majority of numbers in the range was set
let max_set = Number.MIN_VALUE
// For each bit check the
// maximum numbers in the range
// having the jth bit set
for(let j = 0; j < 31; j++){
let total_set = (dp[r][j] - dp[l - 1][j])
max_set = Math.max(max_set, total_set)
}
// Total length of range - count of max
// numbers having 1 bit set in the range
document.write((r - l + 1) - max_set," ")
}
}
// Driver Code
// Initialize the queries
let queries = [[1, 5], [3, 4], [5, 10], [10, 15]]
solve_queries(queries)
// This code is contributed by Shinjanpatra
</script>
Producción
2 1 3 0
Tiempo Complejidad: O(31 * Q)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA