Median of Bitwise XOR of all submatrices starting from the top left corner | Function to find the median of bitwise XOR of all the submatrix whose topmost leftmost corner is ( 0 , 0 ) ; dp [ i ] [ j ] : Stores the bitwise XOR of submatrix having top left corner at ( 0 , 0 ) and bottom right corner at ( i , j ) ; Stores count of submatrix ; Base Case ; Base Case ; Fill dp using tabulation ; Fill dp [ i ] [ j ] ; Driver code
def findMedXOR ( mat , N , M ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( M ) ] for j in range ( N ) ] ; NEW_LINE med = [ 0 ] * ( N * M ) ; NEW_LINE dp [ 0 ] [ 0 ] = mat [ 0 ] [ 0 ] ; NEW_LINE med [ 0 ] = dp [ 0 ] [ 0 ] ; NEW_LINE len = 1 ; NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] ^ mat [ i ] [ 0 ] ; NEW_LINE med [ len ] = dp [ i ] [ 0 ] ; NEW_LINE len += 1 ; NEW_LINE DEDENT for i in range ( 1 , M ) : NEW_LINE INDENT dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] ^ mat [ 0 ] [ i ] ; NEW_LINE med [ len ] = dp [ 0 ] [ i ] ; NEW_LINE len += 1 NEW_LINE DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( 1 , M ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ^ dp [ i ] [ j - 1 ] ^ dp [ i - 1 ] [ j - 1 ] ^ mat [ i ] [ j ] ; NEW_LINE med [ len ] = dp [ i ] [ j ] ; NEW_LINE len += 1 NEW_LINE DEDENT DEDENT med . sort ( ) ; NEW_LINE if ( len % 2 == 0 ) : NEW_LINE INDENT return ( med [ ( len // 2 ) ] + med [ ( len // 2 ) - 1 ] ) / 2.0 ; NEW_LINE DEDENT return med [ len // 2 ] ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 1 , 2 ] , [ 2 , 3 ] ] ; NEW_LINE N = len ( mat [ 0 ] ) ; NEW_LINE M = 2 ; NEW_LINE print ( findMedXOR ( mat , N , M ) ) ; NEW_LINE DEDENT