Eliminaciones mínimas en el rango para hacer bit a bit Y distinto de cero para consultas de rango dado

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *