Queries to find Maximum index R with bitwise AND from index L at least K
Given array A[] of size N and array Q[][2] of size M representing queries of the type {L, K}. The task for this problem is to answer queries for each query to find the largest index R such that bitwise AND of all elements from L to R is at least K. If there is no such index print -1
Examples:
Input: A[] = {15, 14, 17, 42, 34}, Q[][2] = {{1, 7}, {2, 15}, {4, 5}}
Output: 2 -1 5
Explanation:
- first query {L, K} = {1, 7}
- For [L, R] = [1, 1] the bitwise AND value is 15
- For [L, R] = [1, 2] the bitwise AND value is 14
- For [L, R] = [1, 3] the bitwise AND value is 0
- so R = 2 is the largest value for which bitwise AND from L to R is at least K = 7.
- second query {L, K} = {2, 15}
- For [L, R] = [2, 2] the bitwise AND value is 14
- As we go ahead the bitwise AND value will only decrease so in this case R is not possible so answer will be -1
- third query {L, K} = {4, 5}
- For [L, R] = [4, 4] the bitwise AND value is 42
- For [L, R] = [4, 5] the bitwise AND value is 34
- so R = 5 is the largest value for which bitwise AND for L to R is at least K = 5
Input: A[] = {7, 5, 3, 1, 7}, Q[][2] = {{1, 7}, {2, 3}}
Output: 1 2
Explanation:
- first query {L, K} = {1, 7}
- For [L, R] = [1, 1] the bitwise AND value is 7
- For [L, R] = [1, 2] the bitwise AND value is 5
- so R = 1 is the largest value for which bitwise AND from L to R is at least K = 7
- second query {L, K} = {2, 3}
- For [L, R] = [2, 2] the bitwise AND value is 5
- For [L, R] = [2, 3] the bitwise AND value is 1
- so R = 2 is the largest value for which bitwise AND from L to R is at least K = 3
Efficient Approach: To solve the problem follow the below idea:
Binary Search and prefix sum array can be used to solve this problem and the range of binary search will be L to N. f(N) is monotonic function represents whether bitwise AND from L to N is at least K or not. This is binary search of the type TTTTTFFFFFFF. we have to find last time when the function was true using Binary Search. 2d prefix sum array will be used to find bitwise AND between any two ranges [L, R]. For i’th bit if the number of set bit counts are equal to size of range (i.e. R – L + 1) then that bit will be contributing towards bitwise AND of all elements in the given range.
Below are the steps for the above approach:
- Declare 2d array pre[N][32].
- Fill the array by iterating on bits of each N elements.
- Iterate for Q queries
- Set low and high range of binary search.
- ispos() function checks for given R whether bitwise AND from L to R is at least K or not.
- Run while loop till high and low are not equal.
- In while loop find middle element and store it in mid variable.
- Check if bitwise AND from L to mid is at least K or not using ispos() function. If it is true set low = mid else high = mid – 1
- After loop ends if ispos() for high is true then return high else if ispos() is true for low then return low otherwise return -1.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to check if bitwise AND from L to R // is at least K or not bool ispos( int L, int R, int K, vector<vector< int > >& pre) { // size of range int sze = R - L + 1; // to store bitwise AND from L to R int bitwiseANDLtoR = 0; // iterate for ith bit for ( int i = 1; i <= 31; i++) { // number of bits from Range L to R for ith position int numBit = pre[R][i] - pre[L - 1][i]; // if the number of bits in the range L to R // is equal to size of range if (sze == numBit) // i'th bit will contribute 2 ^ (i - 1) bitwiseANDLtoR += (1LL << (i - 1)); } // return true if bitwise AND from L // to R is at least K return bitwiseANDLtoR >= K; } // Function for Queries to find Maximum index R // with bitwise AND from index L at least K int minimizeMaximumAbsDiff( int A[], int N, int Q[][2], int M) { // initialize prefix array vector<vector< int > > pre(N + 1, vector< int >(33, 0)); // Fill prefix array with bits of N elements for ( int i = 0; i < N; i++) { // iterate over all bits for ( int j = 0; j <= 31; j++) { // if j'th bit is set increment prefix array if ((1LL << j) & A[i]) { pre[i + 1][j + 1]++; } } } // Take prefix sum for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= 31; j++) { pre[i][j] += pre[i - 1][j]; } } for ( int i = 0; i < M; i++) { // Range of binary search int low = Q[i][0], high = N; // Running loop till high // is not equal to low while (high - low > 1) { // mid is average of low and high int mid = (low + high) / 2; // Checking test function if (ispos(Q[i][0], mid, Q[i][1], pre)) { low = mid; } else { high = mid - 1; } } // Checking whether high can be answer if (ispos(Q[i][0], high, Q[i][1], pre)) cout << high << " "; // Chekcing whether low can be answer else if (ispos(Q[i][0], low, Q[i][1], pre)) cout << low << " "; else cout << -1 << " "; } cout << endl; } // Driver Code int32_t main() { // Input 1 int N = 5, A[] = { 15, 14, 17, 42, 34 }; int M = 3, Q[][2] = { { 1, 7 }, { 2, 15 }, { 4, 5 } }; // Function Call minimizeMaximumAbsDiff(A, N, Q, M); // Input 2 int N1 = 5, A1[] = { 7, 5, 3, 1, 7 }; int M1 = 2, Q1[][2] = { { 1, 7 }, { 2, 3 } }; // Function Call minimizeMaximumAbsDiff(A1, N1, Q1, M1); return 0; } |
Java
import java.util.*; class GFG { // Function to check if bitwise AND from L to R // is at least K or not static boolean ispos( int L, int R, int K, int [][] pre) { // size of range int sze = R - L + 1 ; // to store bitwise AND from L to R int bitwiseANDLtoR = 0 ; // iterate for ith bit for ( int i = 1 ; i < 32 ; i++) { // number of bits from Range L to R for ith position int numBit = pre[R][i] - pre[L - 1 ][i]; // if the number of bits in the range L to R // is equal to the size of the range if (sze == numBit) { // i'th bit will contribute 2 ^ (i - 1) bitwiseANDLtoR += ( 1 << (i - 1 )); } } // return true if bitwise AND from L // to R is at least K return bitwiseANDLtoR >= K; } // Function for Queries to find Maximum index R // with bitwise AND from index L at least K static void minimizeMaximumAbsDiff( int [] A, int N, int Q, int [][] M) { // initialize prefix array int [][] pre = new int [N + 1 ][ 33 ]; // Fill prefix array with bits of N elements for ( int i = 0 ; i < N; i++) { // iterate over all bits for ( int j = 0 ; j < 32 ; j++) { // if j'th bit is set increment prefix array if (( 1 << j & A[i]) != 0 ) { pre[i + 1 ][j + 1 ] += 1 ; } } } // Take prefix sum for ( int i = 1 ; i <= N; i++) { for ( int j = 1 ; j < 32 ; j++) { pre[i][j] += pre[i - 1 ][j]; } } for ( int i = 0 ; i < Q; i++) { // Range of binary search int low = M[i][ 0 ], high = N; // Running loop until high // is not equal to low while (high - low > 1 ) { // mid is the average of low and high int mid = (low + high) / 2 ; // Checking test function if (ispos(M[i][ 0 ], mid, M[i][ 1 ], pre)) { low = mid; } else { high = mid - 1 ; } } // Checking whether high can be the answer if (ispos(M[i][ 0 ], high, M[i][ 1 ], pre)) { System.out.print(high + " " ); } // Checking whether low can be the answer else if (ispos(M[i][ 0 ], low, M[i][ 1 ], pre)) { System.out.print(low + " " ); } else { System.out.print(- 1 + " " ); } } System.out.println(); } // Driver Code public static void main(String[] args) { // Input 1 int N = 5 ; int [] A = { 15 , 14 , 17 , 42 , 34 }; int M = 3 ; int [][] Q = { { 1 , 7 }, { 2 , 15 }, { 4 , 5 } }; // Function Call minimizeMaximumAbsDiff(A, N, M, Q); // Input 2 int N1 = 5 ; int [] A1 = { 7 , 5 , 3 , 1 , 7 }; int M1 = 2 ; int [][] Q1 = { { 1 , 7 }, { 2 , 3 } }; // Function Call minimizeMaximumAbsDiff(A1, N1, M1, Q1); } } |
Python3
# Function to check if bitwise AND from L to R # is at least K or not def ispos(L, R, K, pre): # size of range sze = R - L + 1 # to store bitwise AND from L to R bitwiseANDLtoR = 0 # iterate for ith bit for i in range ( 1 , 32 ): # number of bits from Range L to R for ith position numBit = pre[R][i] - pre[L - 1 ][i] # if the number of bits in the range L to R # is equal to the size of the range if sze = = numBit: # i'th bit will contribute 2 ^ (i - 1) bitwiseANDLtoR + = ( 1 << (i - 1 )) # return true if bitwise AND from L # to R is at least K return bitwiseANDLtoR > = K # Function for Queries to find Maximum index R # with bitwise AND from index L at least K def minimizeMaximumAbsDiff(A, N, Q, M): # initialize prefix array pre = [[ 0 ] * 33 for _ in range (N + 1 )] # Fill prefix array with bits of N elements for i in range (N): # iterate over all bits for j in range ( 32 ): # if j'th bit is set increment prefix array if ( 1 << j) & A[i]: pre[i + 1 ][j + 1 ] + = 1 # Take prefix sum for i in range ( 1 , N + 1 ): for j in range ( 1 , 32 ): pre[i][j] + = pre[i - 1 ][j] for i in range (M): # Range of binary search low, high = Q[i][ 0 ], N # Running loop until high # is not equal to low while high - low > 1 : # mid is average of low and high mid = (low + high) / / 2 # Checking test function if ispos(Q[i][ 0 ], mid, Q[i][ 1 ], pre): low = mid else : high = mid - 1 # Checking whether high can be the answer if ispos(Q[i][ 0 ], high, Q[i][ 1 ], pre): print (high, end = ' ' ) # Checking whether low can be the answer elif ispos(Q[i][ 0 ], low, Q[i][ 1 ], pre): print (low, end = ' ' ) else : print ( - 1 , end = ' ' ) print () # Driver Code # Input 1 N = 5 A = [ 15 , 14 , 17 , 42 , 34 ] M = 3 Q = [[ 1 , 7 ], [ 2 , 15 ], [ 4 , 5 ]] # Function Call minimizeMaximumAbsDiff(A, N, Q, M) # Input 2 N1 = 5 A1 = [ 7 , 5 , 3 , 1 , 7 ] M1 = 2 Q1 = [[ 1 , 7 ], [ 2 , 3 ]] # Function Call minimizeMaximumAbsDiff(A1, N1, Q1, M1) |
C#
using System; using System.Collections.Generic; class GFG { // Function to check if bitwise AND from L to R // is at least K or not static bool ispos( int L, int R, int K, List<List< int > > pre) { // size of range int sze = R - L + 1; // to store bitwise AND from L to R int bitwiseANDLtoR = 0; // iterate for ith bit for ( int i = 1; i <= 31; i++) { // number of bits from Range L to R for ith // position int numBit = pre[R][i] - pre[L - 1][i]; // if the number of bits in the range L to R // is equal to size of range if (sze == numBit) // i'th bit will contribute 2 ^ (i - 1) bitwiseANDLtoR += (1 << (i - 1)); } // return true if bitwise AND from L // to R is at least K return bitwiseANDLtoR >= K; } // Function for Queries to find Maximum index R // with bitwise AND from index L at least K static void minimizeMaximumAbsDiff( int [] A, int N, int [][] Q, int M) { // initialize prefix array List<List< int > > pre = new List<List< int > >(N + 1); for ( int i = 0; i <= N; i++) { pre.Add( new List< int >(33)); for ( int j = 0; j <= 32; j++) { pre[i].Add(0); } } // Fill prefix array with bits of N elements for ( int i = 0; i < N; i++) { // iterate over all bits for ( int j = 0; j <= 31; j++) { // if j'th bit is set increment prefix array if (((1 << j) & A[i]) != 0) { pre[i + 1][j + 1]++; } } } // Take prefix sum for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= 31; j++) { pre[i][j] += pre[i - 1][j]; } } for ( int i = 0; i < M; i++) { // Range of binary search int low = Q[i][0], high = N; // Running loop till high // is not equal to low while (high - low > 1) { // mid is average of low and high int mid = (low + high) / 2; // Checking test function if (ispos(Q[i][0], mid, Q[i][1], pre)) { low = mid; } else { high = mid - 1; } } // Checking whether high can be answer if (ispos(Q[i][0], high, Q[i][1], pre)) Console.Write(high + " " ); // Chekcing whether low can be answer else if (ispos(Q[i][0], low, Q[i][1], pre)) Console.Write(low + " " ); else Console.Write(-1 + " " ); } Console.WriteLine(); } // Driver Code public static void Main( string [] args) { // Input 1 int N = 5; int [] A = { 15, 14, 17, 42, 34 }; int M = 3; int [][] Q = { new int [] { 1, 7 }, new int [] { 2, 15 }, new int [] { 4, 5 } }; // Function Call minimizeMaximumAbsDiff(A, N, Q, M); // Input 2 int N1 = 5; int [] A1 = { 7, 5, 3, 1, 7 }; int M1 = 2; int [][] Q1 = { new int [] { 1, 7 }, new int [] { 2, 3 } }; // Function Call minimizeMaximumAbsDiff(A1, N1, Q1, M1); } } |
Javascript
// Function to check if bitwise AND from // L to R is at least K or not function ispos(L, R, K, pre) { // size of range const sze = R - L + 1; // to store bitwise AND from L to R let bitwiseANDLtoR = 0; // iterate for ith bit for (let i = 1; i < 32; i++) { // number of bits from Range L to R for ith position const numBit = pre[R][i] - pre[L - 1][i]; // if the number of bits in the range L to R // is equal to the size of the range if (sze === numBit) { // i'th bit will contribute 2 ^ (i - 1) bitwiseANDLtoR += 1 << (i - 1); } } // return true if bitwise AND from L to R is at least K return bitwiseANDLtoR >= K; } // Function for Queries to find Maximum index R // with bitwise AND from index L at least K function minimizeMaximumAbsDiff(A, N, Q, M) { // initialize prefix array const pre = new Array(N + 1).fill().map(() => new Array(33).fill(0)); // Fill prefix array with bits of N elements for (let i = 0; i < N; i++) { // iterate over all bits for (let j = 0; j < 32; j++) { // if j'th bit is set increment prefix array if ((1 << j) & A[i]) { pre[i + 1][j + 1] += 1; } } } // Take prefix sum for (let i = 1; i <= N; i++) { for (let j = 1; j < 32; j++) { pre[i][j] += pre[i - 1][j]; } } for (let i = 0; i < M; i++) { // Range of binary search let low = Q[i][0], high = N; // Running loop until high is not equal to low while (high - low > 1) { // mid is average of low and high const mid = Math.floor((low + high) / 2); // Checking test function if (ispos(Q[i][0], mid, Q[i][1], pre)) { low = mid; } else { high = mid - 1; } } // Checking whether high can be the answer if (ispos(Q[i][0], high, Q[i][1], pre)) { process.stdout.write(`${high} `); } else if (ispos(Q[i][0], low, Q[i][1], pre)) { // Checking whether low can be the answer process.stdout.write(`${low} `); } else { process.stdout.write( '-1 ' ); } } console.log(); } // Driver Code // Input 1 const N = 5; const A = [15, 14, 17, 42, 34]; const M = 3; const Q = [[1, 7], [2, 15], [4, 5]]; // Function Call minimizeMaximumAbsDiff(A, N, Q, M); // Input 2 const N1 = 5; const A1 = [7, 5, 3, 1, 7]; const M1 = 2; const Q1 = [[1, 7], [2, 3]]; // Function Call minimizeMaximumAbsDiff(A1, N1, Q1, M1); |
2 -1 5 1 2
Time Complexity: O(M*logN)
Auxiliary Space: O(1)