Find a sub matrix with maximum XOR
Problem Given a square matrix of side N we have to find a submatrix such that bitwise XOR of its elements is maximum, and we have to print the maximum bitwise XOR.
Examples:
Input : matrix is { {1, 2, 3, 4} {5, 6, 7, 8} {9, 10, 11, 12} {13, 14, 15, 16} } Output : 31 We get the value 31 by doing XOR of submatrix [15, 16}
Naive approach The brute force approach is to find all the submatrix of the array by running four loops two for starting row and column and two for ending row and column and now find the xor of all the elements of the submatrix and finding out the xor and check if the xor of this submatrix is maximum or not.
Time Complexity: O ( n^6 )
Efficient approach In this approach we will calculate the xor of every sub matrix from 1, 1 to i, j this can be done in O (N*N) by using this formula
(xor of submatrix from 1, 1 to i, j ) = (xor of submatrix from 1, 1 to i-1, j )^(xor of submatrix from 1, 1 to i, j-1) ^ (xor of submatrix from 1, 1 to i-1, j-1) ^ arr[i][j] .
Now for calculating xor of sub matrix from i, j to i1, j1 we can use the following formula
(xor of submatrix from i, j to i1, j1) = (xor of submatrix from 1, 1 to i1, j1 )^(xor of submatrix from 1, 1 to i-1, j-1) ^ (xor of submatrix from 1, 1 to i1, j-1) ^ (xor of submatrix from 1, 1 to i-1, j1).
we have to run four loops to find out the all the submatrix of the array and the xor of the submatrix can be calculated in O(1) time.
So the time complexity reduces to O(N^4)
C++
// C++ program to implement the above approach #include <bits/stdc++.h> using namespace std; #define N 101 // Compute the xor of elements from (1, 1) to // (i, j) and store it in prefix_xor[i][j] void prefix( int arr[N][N], int prefix_xor[N][N], int n) { for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { // xor of submatrix from 1, 1 to i, j is // (xor of submatrix from 1, 1 to i-1, // j )^(xor of submatrix from 1, 1 to i, j-1) // ^(xor of submatrix from 1, 1 to i-1, j-1) ^ // arr[i][j] prefix_xor[i][j] = arr[i][j] ^ prefix_xor[i - 1][j] ^ prefix_xor[i][j - 1] ^ prefix_xor[i - 1][j - 1]; } } } // find the submatrix with maximum xor value void Max_xor( int prefix_xor[N][N], int n) { int max_value = 0; // we need four loops to find all the submatrix // of a matrix for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { for ( int i1 = i; i1 <= n; i1++) { for ( int j1 = j; j1 <= n; j1++) { // xor of submatrix from i, j to i1, j1 is // (xor of submatrix from 1, 1 to i1, j1 ) // ^(xor of submatrix from 1, 1 to i-1, j-1) // ^(xor of submatrix from 1, 1 to i1, j-1) // ^(xor of submatrix from 1, 1 to i-1, j1) int x = 0; x ^= prefix_xor[i1][j1]; x ^= prefix_xor[i - 1][j - 1]; x ^= prefix_xor[i1][j - 1]; x ^= prefix_xor[i - 1][j1]; // if the xor is greater than maximum value // substitute it max_value = max(max_value, x); } } } } cout << max_value << endl; } // Driver code int main() { int arr[N][N] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; int n = 4; int prefix_xor[N][N] = { 0 }; // Find the prefix_xor prefix(arr, prefix_xor, n); // Find submatrix with maximum bitwise xor Max_xor(prefix_xor, n); return 0; } |
Java
// Java program to implement the above approach public class GFG { static int N = 101 ; // Compute the xor of elements from (1, 1) to // (i, j) and store it in prefix_xor[i][j] static void prefix( int arr[][], int prefix_xor[][], int n) { for ( int i = 1 ; i < n; i++) { for ( int j = 1 ; j < n; j++) { // xor of submatrix from 1, 1 to i, j is // (xor of submatrix from 1, 1 to i-1, // j )^(xor of submatrix from 1, 1 to i, j-1) // ^(xor of submatrix from 1, 1 to i-1, j-1) ^ // arr[i][j] prefix_xor[i][j] = arr[i][j] ^ prefix_xor[i - 1 ][j] ^ prefix_xor[i][j - 1 ] ^ prefix_xor[i - 1 ][j - 1 ]; } } } // find the submatrix with maximum xor value static void Max_xor( int prefix_xor[][], int n) { int max_value = 0 ; // we need four loops to find all the submatrix // of a matrix for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= n; j++) { for ( int i1 = i; i1 <= n; i1++) { for ( int j1 = j; j1 <= n; j1++) { // xor of submatrix from i, j to i1, j1 is // (xor of submatrix from 1, 1 to i1, j1 ) // ^(xor of submatrix from 1, 1 to i-1, j-1) // ^(xor of submatrix from 1, 1 to i1, j-1) // ^(xor of submatrix from 1, 1 to i-1, j1) int x = 0 ; x ^= prefix_xor[i1][j1]; x ^= prefix_xor[i - 1 ][j - 1 ]; x ^= prefix_xor[i1][j - 1 ]; x ^= prefix_xor[i - 1 ][j1]; // if the xor is greater than maximum value // substitute it max_value = Math.max(max_value, x); } } } } System.out.println(max_value); } // Driver code public static void main(String[] args) { int arr[][] = { { 1 , 2 , 3 , 4 }, { 5 , 6 , 7 , 8 }, { 9 , 10 , 11 , 12 }, { 13 , 14 , 15 , 16 } }; int n = 4 ; int prefix_xor[][] = new int [N][N]; // Find the prefix_xor prefix(arr, prefix_xor, n); // Find submatrix with maximum bitwise xor Max_xor(prefix_xor, n); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement the above approach N = 101 # Compute the xor of elements from (1, 1) to # (i, j) and store it in prefix_xor[i][j] def prefix(arr, prefix_xor, n): for i in range ( 1 , n): for j in range ( 1 , n): # xor of submatrix from 1, 1 to i, j is # (xor of submatrix from 1, 1 to i-1, # j )^(xor of submatrix from 1, 1 to i, j-1) # ^(xor of submatrix from 1, 1 to i-1, j-1) ^ # arr[i][j] prefix_xor[i][j] = (arr[i][j] ^ prefix_xor[i - 1 ][j] ^ prefix_xor[i][j - 1 ] ^ prefix_xor[i - 1 ][j - 1 ]) # find the submatrix with maximum xor value def Max_xor(prefix_xor, n): max_value = 0 # we need four loops to find # all the submatrix of a matrix for i in range ( 1 , n + 1 ): for j in range ( 1 , n + 1 ): for i1 in range (i, n + 1 ): for j1 in range (j, n + 1 ): # xor of submatrix from i, j to i1, j1 is # (xor of submatrix from 1, 1 to i1, j1 ) # ^(xor of submatrix from 1, 1 to i-1, j-1) # ^(xor of submatrix from 1, 1 to i1, j-1) # ^(xor of submatrix from 1, 1 to i-1, j1) x = 0 x ^ = prefix_xor[i1][j1] x ^ = prefix_xor[i - 1 ][j - 1 ] x ^ = prefix_xor[i1][j - 1 ] x ^ = prefix_xor[i - 1 ][j1] # if the xor is greater than maximum value # substitute it max_value = max (max_value, x) print (max_value) # Driver code arr = [[ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ], [ 9 , 10 , 11 , 12 ], [ 13 , 14 , 15 , 16 ]] n = 4 prefix_xor = [[ 0 for i in range (N)] for i in range (N)] # Find the prefix_xor prefix(arr, prefix_xor, n) # Find submatrix with maximum bitwise xor Max_xor(prefix_xor, n) # This code is contributed by Mohit Kumar |
C#
// C# program to implement the above approach using System; using System.Collections.Generic; public class GFG { static int N =101; // Compute the xor of elements from (1, 1) to // (i, j) and store it in prefix_xor[i,j] static void prefix( int [,]arr, int [,]prefix_xor, int n) { for ( int i = 1; i < n; i++) { for ( int j = 1; j < n; j++) { // xor of submatrix from 1, 1 to i, j is // (xor of submatrix from 1, 1 to i-1, // j )^(xor of submatrix from 1, 1 to i, j-1) // ^(xor of submatrix from 1, 1 to i-1, j-1) ^ // arr[i,j] prefix_xor[i,j] = arr[i,j] ^ prefix_xor[i - 1,j] ^ prefix_xor[i,j - 1] ^ prefix_xor[i - 1,j - 1]; } } } // find the submatrix with maximum xor value static void Max_xor( int [,]prefix_xor, int n) { int max_value = 0; // we need four loops to find all the submatrix // of a matrix for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { for ( int i1 = i; i1 <= n; i1++) { for ( int j1 = j; j1 <= n; j1++) { // xor of submatrix from i, j to i1, j1 is // (xor of submatrix from 1, 1 to i1, j1 ) // ^(xor of submatrix from 1, 1 to i-1, j-1) // ^(xor of submatrix from 1, 1 to i1, j-1) // ^(xor of submatrix from 1, 1 to i-1, j1) int x = 0; x ^= prefix_xor[i1, j1]; x ^= prefix_xor[i - 1, j - 1]; x ^= prefix_xor[i1, j - 1]; x ^= prefix_xor[i - 1, j1]; // if the xor is greater than maximum value // substitute it max_value = Math.Max(max_value, x); } } } } Console.WriteLine(max_value); } // Driver code public static void Main(String[] args) { int [,]arr = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; int n = 4; int [,]prefix_xor = new int [N,N]; // Find the prefix_xor prefix(arr, prefix_xor, n); // Find submatrix with maximum bitwise xor Max_xor(prefix_xor, n); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to implement the above approach var N = 101; // Compute the xor of elements from (1, 1) to // (i, j) and store it in prefix_xor[i][j] function prefix(arr, prefix_xor, n) { for ( var i = 1; i < n; i++) { for ( var j = 1; j < n; j++) { // xor of submatrix from 1, 1 to i, j is // (xor of submatrix from 1, 1 to i-1, // j )^(xor of submatrix from 1, 1 to i, j-1) // ^(xor of submatrix from 1, 1 to i-1, j-1) ^ // arr[i][j] prefix_xor[i][j] = arr[i][j] ^ prefix_xor[i - 1][j] ^ prefix_xor[i][j - 1] ^ prefix_xor[i - 1][j - 1]; } } } // find the submatrix with maximum xor value function Max_xor(prefix_xor, n) { var max_value = 0; // we need four loops to find all the submatrix // of a matrix for ( var i = 1; i <= n; i++) { for ( var j = 1; j <= n; j++) { for ( var i1 = i; i1 <= n; i1++) { for ( var j1 = j; j1 <= n; j1++) { // xor of submatrix from i, j to i1, j1 is // (xor of submatrix from 1, 1 to i1, j1 ) // ^(xor of submatrix from 1, 1 to i-1, j-1) // ^(xor of submatrix from 1, 1 to i1, j-1) // ^(xor of submatrix from 1, 1 to i-1, j1) var x = 0; x ^= prefix_xor[i1][j1]; x ^= prefix_xor[i - 1][j - 1]; x ^= prefix_xor[i1][j - 1]; x ^= prefix_xor[i - 1][j1]; // if the xor is greater than maximum value // substitute it max_value = Math.max(max_value, x); } } } } document.write( max_value ); } // Driver code var arr = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ] ]; var n = 4; var prefix_xor = Array.from(Array(N), () => Array(N).fill(0)); // Find the prefix_xor prefix(arr, prefix_xor, n); // Find submatrix with maximum bitwise xor Max_xor(prefix_xor, n); // This code is contributed by rutvik_56. </script> |
31
Time Complexity: O(n4)
Auxiliary Space: O(1)
Contact Us