Find a sub matrix with maximum XOR | C ++ program to implement the above approach ; Compute the xor of elements from ( 1 , 1 ) to ( i , j ) and store it in prefix_xor [ i ] [ 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 ] ; find the submatrix with maximum xor value ; we need four loops to find all the submatrix of a matrix ; 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 ) ; if the xor is greater than maximum value substitute it ; Driver code ; Find the prefix_xor ; Find submatrix with maximum bitwise xor
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  101 NEW_LINE 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 ++ ) { prefix_xor [ i ] [ j ] = arr [ i ] [ j ] ^ prefix_xor [ i - 1 ] [ j ] ^ prefix_xor [ i ] [ j - 1 ] ^ prefix_xor [ i - 1 ] [ j - 1 ] ; } } } void Max_xor ( int prefix_xor [ N ] [ N ] , int n ) { int max_value = 0 ; 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 ++ ) { 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 ] ; max_value = max ( max_value , x ) ; } } } } cout << max_value << endl ; } 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 } ; prefix ( arr , prefix_xor , n ) ; Max_xor ( prefix_xor , n ) ; return 0 ; }