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
function findMedXOR ( mat , N , M ) { let dp = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) dp [ i ] = new Array ( M ) ; let med = new Array ( N * M ) ; dp [ 0 ] [ 0 ] = mat [ 0 ] [ 0 ] ; med [ 0 ] = dp [ 0 ] [ 0 ] ; let len = 1 ; for ( let i = 1 ; i < N ; i ++ ) { dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] ^ mat [ i ] [ 0 ] ; med [ len ++ ] = dp [ i ] [ 0 ] ; } for ( let i = 1 ; i < M ; i ++ ) { dp [ 0 ] [ i ] = dp [ 0 ] [ i - 1 ] ^ mat [ 0 ] [ i ] ; med [ len ++ ] = dp [ 0 ] [ i ] ; } for ( let i = 1 ; i < N ; i ++ ) { for ( let j = 1 ; j < M ; j ++ ) { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ^ dp [ i ] [ j - 1 ] ^ dp [ i - 1 ] [ j - 1 ] ^ mat [ i ] [ j ] ; med [ len ++ ] = dp [ i ] [ j ] ; } } med . sort ( ) ; if ( len % 2 == 0 ) { return ( med [ parseInt ( len / 2 ) ] + med [ parseInt ( len / 2 ) - 1 ] ) / 2.0 ; } return med [ parseInt ( len / 2 ) ] ; } let mat = [ [ 1 , 2 ] , [ 2 , 3 ] ] ; let N = mat . length ; let M = 2 ; document . write ( findMedXOR ( mat , N , M ) ) ;