Given an N * N matrix mat[][] consisting of non-negative integers and some queries consisting of top-left and bottom-right corner of the sub-matrix, the task is to find the bit-wise AND of all the elements of the sub-matrix given in each query.
Examples:
Input: mat[][] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}},
q[] = {{1, 1, 1, 1}, {1, 2, 2, 2}}
Output:
5
0
Query 1: Only element in the sub-matrix is 5.
Query 2: 6 AND 9 = 0Input: mat[][] = {
{12, 23, 13},
{41, 15, 46},
{75, 82, 123}},
q[] = {{0, 0, 2, 2}, {1, 1, 2, 2}}
Output:
0
2
Naive approach: Iterate through the sub-matrix and find the bit-wise AND of all the numbers in that range. This will take O(n2) time for each query in the worst case.
Efficient approach: If we look at the integers as binary number, we can easily see that condition for ith bit of our answer to be set is that ith bit of all the integers in the sub-matrix should be set.
So, we will calculate prefix-count for each bit. We will use this to find the number of integers in the sub-matrix with ith bit set. If it is equal to the total elements of the sub-matrix then the ith bit of our answer will also be set.
For this, we will create a 3d-array, prefix_count[][][] where prefix_count[i][x][y] will store the count of all the elements of the sub-matrix with top left corner at {0, 0} and bottom right corner at {x, y} and ith bit set. Refer
this article to understand prefix_count in case of matrix.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define bitscount 32#define n 3using namespace std;// Array to store bit-wise// prefix countint prefix_count[bitscount][n][n];// Function to find the prefix sumvoid findPrefixCount(int arr[][n]){ // Loop for each bit for (int i = 0; i < bitscount; i++) { // Loop to find prefix-count // for each row for (int j = 0; j < n; j++) { prefix_count[i][j][0] = ((arr[j][0] >> i) & 1); for (int k = 1; k < n; k++) { prefix_count[i][j][k] = ((arr[j][k] >> i) & 1); prefix_count[i][j][k] += prefix_count[i][j][k - 1]; } } } // Finding column-wise prefix // count for (int i = 0; i < bitscount; i++) for (int j = 1; j < n; j++) for (int k = 0; k < n; k++) prefix_count[i][j][k] += prefix_count[i][j - 1][k];}// Function to return the result for a queryint rangeAnd(int x1, int y1, int x2, int y2){ // To store the answer int ans = 0; // Loop for each bit for (int i = 0; i < bitscount; i++) { // To store the number of variables // with ith bit set int p; if (x1 == 0 and y1 == 0) p = prefix_count[i][x2][y2]; else if (x1 == 0) p = prefix_count[i][x2][y2] - prefix_count[i][x2][y1 - 1]; else if (y1 == 0) p = prefix_count[i][x2][y2] - prefix_count[i][x1 - 1][y2]; else p = prefix_count[i][x2][y2] - prefix_count[i][x1 - 1][y2] - prefix_count[i][x2][y1 - 1] + prefix_count[i][x1 - 1][y1 - 1]; // If count of variables whose ith bit // is set equals to the total // elements in the sub-matrix if (p == (x2 - x1 + 1) * (y2 - y1 + 1)) ans = (ans | (1 << i)); } return ans;}// Driver codeint main(){ int arr[][n] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; findPrefixCount(arr); int queries[][4] = { { 1, 1, 1, 1 }, { 1, 2, 2, 2 } }; int q = sizeof(queries) / sizeof(queries[0]); for (int i = 0; i < q; i++) cout << rangeAnd(queries[i][0], queries[i][1], queries[i][2], queries[i][3]) << endl; return 0;} |
Java
// Java implementation of the approach class GFG{ final static int bitscount = 32 ; final static int n = 3 ; // Array to store bit-wise // prefix count static int prefix_count[][][] = new int [bitscount][n][n]; // Function to find the prefix sum static void findPrefixCount(int arr[][]) { // Loop for each bit for (int i = 0; i < bitscount; i++) { // Loop to find prefix-count // for each row for (int j = 0; j < n; j++) { prefix_count[i][j][0] = ((arr[j][0] >> i) & 1); for (int k = 1; k < n; k++) { prefix_count[i][j][k] = ((arr[j][k] >> i) & 1); prefix_count[i][j][k] += prefix_count[i][j][k - 1]; } } } // Finding column-wise prefix // count for (int i = 0; i < bitscount; i++) for (int j = 1; j < n; j++) for (int k = 0; k < n; k++) prefix_count[i][j][k] += prefix_count[i][j - 1][k]; } // Function to return the result for a query static int rangeAnd(int x1, int y1, int x2, int y2) { // To store the answer int ans = 0; // Loop for each bit for (int i = 0; i < bitscount; i++) { // To store the number of variables // with ith bit set int p; if (x1 == 0 && y1 == 0) p = prefix_count[i][x2][y2]; else if (x1 == 0) p = prefix_count[i][x2][y2] - prefix_count[i][x2][y1 - 1]; else if (y1 == 0) p = prefix_count[i][x2][y2] - prefix_count[i][x1 - 1][y2]; else p = prefix_count[i][x2][y2] - prefix_count[i][x1 - 1][y2] - prefix_count[i][x2][y1 - 1] + prefix_count[i][x1 - 1][y1 - 1]; // If count of variables whose ith bit // is set equals to the total // elements in the sub-matrix if (p == (x2 - x1 + 1) * (y2 - y1 + 1)) ans = (ans | (1 << i)); } return ans; } // Driver code public static void main (String[] args) { int arr[][] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; findPrefixCount(arr); int queries[][] = { { 1, 1, 1, 1 }, { 1, 2, 2, 2 } }; int q = queries.length; for (int i = 0; i < q; i++) System.out.println( rangeAnd(queries[i][0], queries[i][1], queries[i][2], queries[i][3]) ); }}// This code is contributed by AnkitRai |
Python3
# Python 3 implementation of the approachbitscount = 32n = 3# Array to store bit-wise# prefix countprefix_count = [[[0 for i in range(n)] for j in range(n)] for k in range(bitscount)]# Function to find the prefix sumdef findPrefixCount(arr): # Loop for each bit for i in range(bitscount): # Loop to find prefix-count # for each row for j in range(n): prefix_count[i][j][0] = ((arr[j][0] >> i) & 1) for k in range(1,n): prefix_count[i][j][k] = ((arr[j][k] >> i) & 1) prefix_count[i][j][k] += prefix_count[i][j][k - 1] # Finding column-wise prefix # count for i in range(bitscount): for j in range(1,n): for k in range(n): prefix_count[i][j][k] += prefix_count[i][j - 1][k]# Function to return the result for a querydef rangeOr(x1, y1, x2, y2): # To store the answer ans = 0 # Loop for each bit for i in range(bitscount): # To store the number of variables # with ith bit set if (x1 == 0 and y1 == 0): p = prefix_count[i][x2][y2] elif (x1 == 0): p = prefix_count[i][x2][y2] - prefix_count[i][x2][y1 - 1] elif (y1 == 0): p = prefix_count[i][x2][y2] - prefix_count[i][x1 - 1][y2] else: p = prefix_count[i][x2][y2] - prefix_count[i][x1 - 1][y2] - prefix_count[i][x2][y1 - 1] + prefix_count[i][x1 - 1][y1 - 1]; # If count of variables with ith bit # set is greater than 0 if (p == (x2 - x1 + 1) * (y2 - y1 + 1)): ans = (ans | (1 << i)) return ans# Driver codeif __name__ == '__main__': arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] findPrefixCount(arr) queries = [[1, 1, 1, 1], [1, 2, 2, 2]] q = len(queries) for i in range(q): print(rangeOr(queries[i][0],queries[i][1],queries[i][2],queries[i][3]))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System; class GFG{ static int bitscount = 32 ; static int n = 3 ; // Array to store bit-wise // prefix count static int [,,]prefix_count = new int [bitscount,n,n]; // Function to find the prefix sum static void findPrefixCount(int [,]arr) { // Loop for each bit for (int i = 0; i < bitscount; i++) { // Loop to find prefix-count // for each row for (int j = 0; j < n; j++) { prefix_count[i,j,0] = ((arr[j,0] >> i) & 1); for (int k = 1; k < n; k++) { prefix_count[i, j, k] = ((arr[j,k] >> i) & 1); prefix_count[i, j, k] += prefix_count[i, j, k - 1]; } } } // Finding column-wise prefix // count for (int i = 0; i < bitscount; i++) for (int j = 1; j < n; j++) for (int k = 0; k < n; k++) prefix_count[i, j, k] += prefix_count[i, j - 1, k]; } // Function to return the result for a query static int rangeAnd(int x1, int y1, int x2, int y2) { // To store the answer int ans = 0; // Loop for each bit for (int i = 0; i < bitscount; i++) { // To store the number of variables // with ith bit set int p; if (x1 == 0 && y1 == 0) p = prefix_count[i, x2, y2]; else if (x1 == 0) p = prefix_count[i, x2, y2] - prefix_count[i, x2, y1 - 1]; else if (y1 == 0) p = prefix_count[i, x2, y2] - prefix_count[i, x1 - 1, y2]; else p = prefix_count[i, x2, y2] - prefix_count[i, x1 - 1, y2] - prefix_count[i, x2, y1 - 1] + prefix_count[i, x1 - 1, y1 - 1]; // If count of variables whose ith bit // is set equals to the total // elements in the sub-matrix if (p == (x2 - x1 + 1) * (y2 - y1 + 1)) ans = (ans | (1 << i)); } return ans; } // Driver code public static void Main (String[] args) { int [,]arr = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; findPrefixCount(arr); int [,]queries = { { 1, 1, 1, 1 }, { 1, 2, 2, 2 } }; int q = queries.GetLength(0); for (int i = 0; i < q; i++) Console.WriteLine( rangeAnd(queries[i,0], queries[i,1], queries[i,2], queries[i,3]) ); }}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// Javascript implementation of the approach let bitscount = 32;let n = 3 ;// Array to store bit-wise // prefix count let prefix_count = new Array(bitscount); for(let i = 0; i < bitscount; i++){ prefix_count[i] = new Array(n); for(let j = 0; j < n; j++) { prefix_count[i][j] = new Array(n); for(let k = 0; k < n; k++) { prefix_count[i][j][k] = 0; } }}// Function to find the prefix sum function findPrefixCount(arr) { // Loop for each bit for(let i = 0; i < bitscount; i++) { // Loop to find prefix-count // for each row for(let j = 0; j < n; j++) { prefix_count[i][j][0] = ((arr[j][0] >> i) & 1); for(let k = 1; k < n; k++) { prefix_count[i][j][k] = ( (arr[j][k] >> i) & 1); prefix_count[i][j][k] += prefix_count[i][j][k - 1]; } } } // Finding column-wise prefix // count for(let i = 0; i < bitscount; i++) for(let j = 1; j < n; j++) for(let k = 0; k < n; k++) prefix_count[i][j][k] += prefix_count[i][j - 1][k]; } // Function to return the result for a query function rangeAnd(x1, y1, x2, y2) { // To store the answer let ans = 0; // Loop for each bit for(let i = 0; i < bitscount; i++) { // To store the number of variables // with ith bit set let p; if (x1 == 0 && y1 == 0) p = prefix_count[i][x2][y2]; else if (x1 == 0) p = prefix_count[i][x2][y2] - prefix_count[i][x2][y1 - 1]; else if (y1 == 0) p = prefix_count[i][x2][y2] - prefix_count[i][x1 - 1][y2]; else p = prefix_count[i][x2][y2] - prefix_count[i][x1 - 1][y2] - prefix_count[i][x2][y1 - 1] + prefix_count[i][x1 - 1][y1 - 1]; // If count of variables whose ith bit // is set equals to the total // elements in the sub-matrix if (p == (x2 - x1 + 1) * (y2 - y1 + 1)) ans = (ans | (1 << i)); } return ans; }// Driver codelet arr = [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]; findPrefixCount(arr); let queries = [ [ 1, 1, 1, 1 ], [ 1, 2, 2, 2 ] ]; let q = queries.length; for(let i = 0; i < q; i++) document.write(rangeAnd(queries[i][0], queries[i][1], queries[i][2], queries[i][3]) + "</br>"); // This code is contributed by divyeshrabadiya07</script> |
Output:
5 0
Time complexity for pre-computation is O(n2) and each query can be answered in O(1)
Auxiliary Space: O(n2)
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!
