Bitwise Operations in Subarrays: Query and Result
Given a positive integer array A[] of size N and Q queries. Given a 2D integer array Queries[][] of length Q where each query has four integers l1, r1, l2, r2, the task is to calculate (Al1 & Al1+1 & Al1+2 …& Ar1) | (Al2 & Al2+1 & Al2+2….& Ar2) and return an integer array answer of length Q where answer[i] represents the answer for ith query.
Examples:
Input: N = 5, Q = 2, A[] = {2, 3, 7, 11, 15}, Queries[][] = {{2, 4, 3, 5}, {1, 5, 2, 3}}
Output: {3, 3}
Explanation:
- for query 2 4 3 5: answer = (3&7&11) | (7&11&15) = (3) | (3) = 3
- for query 1 5 2 3: answer = (2&3&7&11&15) | (3&7) = (2) | (3) = 3
Input: N = 6, Q = 2, A[] = {3, 7, 13, 12, 14, 15}, Queries[][] = {{1, 4, 2, 5}, {1, 2, 3, 6}}
Output: {4 15}
Explanation:
- for query 1 4 2 5: answer = (3&7&13&12) | (7&13&12&14) = (0) | (4) = 4
- for query 1 2 3 6: answer = (3&7) | (13&12&14&15) = (3) | (12) = 15
Approach: This can be solved with the following idea:
The intuition behind this solution is to utilize bitwise operations efficiently. By pre-calculating the counts of each bit up to a certain index, the code can quickly determine if a particular bit position is set in a given subarray. The final answer is calculated by performing bitwise OR operations for the bits that satisfy the conditions specified in the query.
Below are the steps involved:
- pre is initialized as an empty list to store the prefix counts for each bit.
- bit is initialized as a list of 30 zeroes, which will be used to count the occurrences of each bit in the array A.
- The initial state of bit is appended to pre as the first element.
- The code then iterates through each element e in array A and for each bit position (from 0 to 29), it checks if the bit is set.
- If it is set, it increments the count of that bit position in the bit array.
- After each iteration through the elements of A, a copy of the current state of the bit array is appended to the pre array. This allows us to keep track of the cumulative counts of each bit up to a certain index in A.
- The code initializes an empty list res to store the results for each query.
- It initializes ans as 0, which will be the answer for each query.
- For each query, it calculates the lengths d1 and d2 based on the ranges provided in the query.
- It then iterates through each bit position from 0 to 29 and checks if either of the subarrays (defined by the query ranges) has all the bits set for that position. If it finds such a position, it adds 2^i (i.e., 1 << i) to the answer ans.
- Finally, it appends the answer ans for the current query to the result list res.
Below is the implementation of the code:
C++
// C++ code for the above approach: #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to find minimum query vector< int > minQuery( int N, int Q, vector< int >& A, vector<vector< int > >& Queries) { // Intialize a 2D vector vector<vector< int > > v(N + 1, vector< int >(31, 0)); // Iterate in given array for ( int i = 1; i <= N; i++) { // Iterate for 31 bits for ( int j = 0; j < 31; j++) { v[i][j] = v[i - 1][j] + ((A[i - 1] >> j) & 1); } } vector< int > ans(Q); for ( int i = 0; i < Q; i++) { int a1 = 0; int a2 = 0; // Iterate for queries int l1 = Queries[i][0], r1 = Queries[i][1], l2 = Queries[i][2], r2 = Queries[i][3]; for ( int j = 0; j < 31; j++) { if (v[r1][j] - v[l1 - 1][j] == (r1 - l1 + 1)) a1 += (1 << j); if (v[r2][j] - v[l2 - 1][j] == (r2 - l2 + 1)) a2 += (1 << j); } // Do OR of a1 and a2 ans[i] = (a1 | a2); } return ans; } // Driver code int main() { int N = 5; int Q = 2; vector< int > A = { 2, 3, 7, 11, 15 }; vector<vector< int > > Queries = { { 2, 4, 3, 5 }, { 1, 5, 2, 3 } }; // Function call vector< int > ans = minQuery(N, Q, A, Queries); for ( auto a : ans) { cout << a << " "; } return 0; } |
Java
import java.util.ArrayList; import java.util.List; public class MinimumQuery { // Function to find minimum query static List<Integer> minQuery( int N, int Q, List<Integer> A, List<List<Integer>> Queries) { // Initialize a 2D array int [][] v = new int [N + 1 ][ 31 ]; // Iterate in the given array for ( int i = 1 ; i <= N; i++) { // Iterate for 31 bits for ( int j = 0 ; j < 31 ; j++) { v[i][j] = v[i - 1 ][j] + ((A.get(i - 1 ) >> j) & 1 ); } } List<Integer> ans = new ArrayList<>(); for ( int i = 0 ; i < Q; i++) { int a1 = 0 ; int a2 = 0 ; // Iterate for queries int l1 = Queries.get(i).get( 0 ), r1 = Queries.get(i).get( 1 ), l2 = Queries.get(i).get( 2 ), r2 = Queries.get(i).get( 3 ); for ( int j = 0 ; j < 31 ; j++) { if (v[r1][j] - v[l1 - 1 ][j] == (r1 - l1 + 1 )) a1 += ( 1 << j); if (v[r2][j] - v[l2 - 1 ][j] == (r2 - l2 + 1 )) a2 += ( 1 << j); } // Do OR of a1 and a2 ans.add(a1 | a2); } return ans; } // Driver code public static void main(String[] args) { int N = 5 ; int Q = 2 ; List<Integer> A = List.of( 2 , 3 , 7 , 11 , 15 ); List<List<Integer>> Queries = List.of( List.of( 2 , 4 , 3 , 5 ), List.of( 1 , 5 , 2 , 3 ) ); // Function call List<Integer> ans = minQuery(N, Q, A, Queries); for ( int a : ans) { System.out.print(a + " " ); } } } |
Python3
def min_query(N, Q, A, Queries): # Initialize a 2D list v = [[ 0 ] * 31 for _ in range (N + 1 )] # Iterate through the given array for i in range ( 1 , N + 1 ): # Iterate for 31 bits for j in range ( 31 ): v[i][j] = v[i - 1 ][j] + ((A[i - 1 ] >> j) & 1 ) ans = [] for i in range (Q): a1 = 0 a2 = 0 # Iterate through queries l1, r1, l2, r2 = Queries[i] for j in range ( 31 ): if v[r1][j] - v[l1 - 1 ][j] = = (r1 - l1 + 1 ): a1 + = ( 1 << j) if v[r2][j] - v[l2 - 1 ][j] = = (r2 - l2 + 1 ): a2 + = ( 1 << j) # Do OR of a1 and a2 ans.append(a1 | a2) return ans # Driver code if __name__ = = "__main__" : N = 5 Q = 2 A = [ 2 , 3 , 7 , 11 , 15 ] Queries = [[ 2 , 4 , 3 , 5 ], [ 1 , 5 , 2 , 3 ]] # Function call result = min_query(N, Q, A, Queries) # Output the result for res in result: print (res, end = " " ) |
C#
using System; using System.Collections.Generic; class Program { // Function to find minimum query static List< int > MinQuery( int N, int Q, List< int > A, List<List< int >> Queries) { // Initialize a 2D list List<List< int >> v = new List<List< int >>(N + 1); for ( int i = 0; i <= N; i++) { v.Add( new List< int >( new int [31])); } // Iterate in the given array for ( int i = 1; i <= N; i++) { // Iterate for 31 bits for ( int j = 0; j < 31; j++) { v[i][j] = v[i - 1][j] + ((A[i - 1] >> j) & 1); } } List< int > ans = new List< int >(Q); for ( int i = 0; i < Q; i++) { int a1 = 0; int a2 = 0; // Iterate for queries int l1 = Queries[i][0], r1 = Queries[i][1], l2 = Queries[i][2], r2 = Queries[i][3]; for ( int j = 0; j < 31; j++) { if (v[r1][j] - v[l1 - 1][j] == (r1 - l1 + 1)) a1 += (1 << j); if (v[r2][j] - v[l2 - 1][j] == (r2 - l2 + 1)) a2 += (1 << j); } // Do OR of a1 and a2 ans.Add(a1 | a2); } return ans; } // Driver code static void Main() { int N = 5; int Q = 2; List< int > A = new List< int > { 2, 3, 7, 11, 15 }; List<List< int >> Queries = new List<List< int >> { new List< int > { 2, 4, 3, 5 }, new List< int > { 1, 5, 2, 3 } }; // Function call List< int > result = MinQuery(N, Q, A, Queries); // Print the results foreach ( var a in result) { Console.Write($ "{a} " ); } } } |
Javascript
// Function to find minimum query function minQuery(N, Q, A, Queries) { // Initialize a 2D array let v = new Array(N + 1); for (let i = 0; i <= N; i++) { v[i] = new Array(31).fill(0); } // Iterate through the given array for (let i = 1; i <= N; i++) { // Iterate for 31 bits for (let j = 0; j < 31; j++) { v[i][j] = v[i - 1][j] + ((A[i - 1] >> j) & 1); } } let ans = new Array(Q); for (let i = 0; i < Q; i++) { let a1 = 0; let a2 = 0; // Iterate for queries let [l1, r1, l2, r2] = Queries[i]; for (let j = 0; j < 31; j++) { if (v[r1][j] - v[l1 - 1][j] === r1 - l1 + 1) { a1 += (1 << j); } if (v[r2][j] - v[l2 - 1][j] === r2 - l2 + 1) { a2 += (1 << j); } } // Do OR of a1 and a2 ans[i] = (a1 | a2); } return ans; } // Driver code function main() { let N = 5; let Q = 2; let A = [2, 3, 7, 11, 15]; let Queries = [[2, 4, 3, 5], [1, 5, 2, 3]]; // Function call let result = minQuery(N, Q, A, Queries); console.log(result.join( ' ' )); } // Run the main function main(); |
3 3
Time Complexity: O(N + Q)
Auxiliary Space: O(N)
Contact Us