Find a sub matrix with maximum XOR | Python3 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
N = 101 NEW_LINE def prefix ( arr , prefix_xor , n ) : NEW_LINE INDENT for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( 1 , n ) : NEW_LINE INDENT prefix_xor [ i ] [ j ] = ( arr [ i ] [ j ] ^ prefix_xor [ i - 1 ] [ j ] ^ prefix_xor [ i ] [ j - 1 ] ^ prefix_xor [ i - 1 ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT def Max_xor ( prefix_xor , n ) : NEW_LINE INDENT max_value = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT for i1 in range ( i , n + 1 ) : NEW_LINE INDENT for j1 in range ( j , n + 1 ) : NEW_LINE INDENT x = 0 NEW_LINE x ^= prefix_xor [ i1 ] [ j1 ] NEW_LINE x ^= prefix_xor [ i - 1 ] [ j - 1 ] NEW_LINE x ^= prefix_xor [ i1 ] [ j - 1 ] NEW_LINE x ^= prefix_xor [ i - 1 ] [ j1 ] NEW_LINE max_value = max ( max_value , x ) NEW_LINE DEDENT DEDENT DEDENT DEDENT print ( max_value ) NEW_LINE DEDENT arr = [ [ 1 , 2 , 3 , 4 ] , [ 5 , 6 , 7 , 8 ] , [ 9 , 10 , 11 , 12 ] , [ 13 , 14 , 15 , 16 ] ] NEW_LINE n = 4 NEW_LINE prefix_xor = [ [ 0 for i in range ( N ) ] for i in range ( N ) ] NEW_LINE prefix ( arr , prefix_xor , n ) NEW_LINE Max_xor ( prefix_xor , n ) NEW_LINE