Given an array queries[][] of Q range queries, the task is to find the minimum removals from the range[l, r] such that the bitwise AND of the range is a non-zero value.
Examples:
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
Naive Approach: This can be solved by iterating through every range and checking the max count of elements in the range having the common set bit and removing that from the total count of element i.e (r – l + 1).
Below is the implementation of the above approach:
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-zerovoid 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 Codeint 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 approachimport 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-zerodef 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 queriesqueries = [[1, 5], [3, 4], [5, 10], [10, 15]]solve_queries(queries)# This code is contributed by gfgking |
C#
// C# code to implement the above approachusing 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-zeroconst 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 querieslet queries = [ [ 1, 5 ], [ 3, 4 ], [ 5, 10 ], [ 10, 15 ] ];solve_queries(queries);// This code is contributed by rakeshsahni</script> |
Output
2 1 3 0
Time Complexity: O (31 * Q * n ) where n is the length of the maximum range.
Auxiliary Space: O(1)
Efficient Approach: This approach is based on Dynamic programming and prefix sum technique. This can be done by storing the count of total set bits till that range in a using dp[] array at each position of 31 bits. Here the state of dp[i][j] means that the total set bits of jth bit position till i from [1, i]. Follow these steps to solve the above problem:
- Make a function call to count_set_bits() to precalculate the dp[][] array using prefix sum.
- Now iterate through the queries and assign l = q[i][0], r = q[i][1].
- Initialize max_set = INT_MIN to store the count of the max count of elements in the range having the j-th bit set.
- Iterate through the bits from [0, 30].
- Count the number of elements having j-th bit set by total_set = (dp[r][j] – dp[l – 1][j]).
- Store the max count of elements having j-th bit set by taking max(max_set, total_set).
- Print the minimum removals required by subtracting max_set from the total length (r-l+1).
Below is the implementation of the above approach:
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 queriesvoid 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 Codeint 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 approachimport 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 approachdp = [[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 queriesdef 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 queriesqueries = [[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 approachusing 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 approachlet 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 queriesfunction 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 querieslet queries = [[1, 5], [3, 4], [5, 10], [10, 15]]solve_queries(queries)// This code is contributed by Shinjanpatra</script> |
Output
2 1 3 0
Time Complexity: O(31 * (Q+n))
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
