Sum of bitwise AND of all submatrices | Javascript program to find sum of Bit - wise AND of all submatrices ; Function to find prefix - count for each row from right to left ; Function to find the number of submatrices with all 1 s ; Array to store required prefix count of 1 s from right to left for boolean array ; Variable to store the final answer ; For each index of a column , determine the number of sub - matrices starting from that index and has all 1 s ; Stack to store elements and the count of the numbers they popped First part of pair is value of inserted element Second part is count of the number of elements pushed before with a greater value ; variable to store the number of submatrices with all 1 s ; Function to find the sum of Bitwise - AND of all submatrices ; matrix to store the status of ith bit of each element of matrix arr ; Driver Code
var n = 3 ; function findPrefixCount ( p_arr , set_bit ) { for ( var i = 0 ; i < n ; i ++ ) { for ( var j = n - 1 ; j >= 0 ; j -- ) { if ( ! set_bit [ i ] [ j ] ) continue ; if ( j != n - 1 ) p_arr [ i ] [ j ] += p_arr [ i ] [ j + 1 ] ; p_arr [ i ] [ j ] += set_bit [ i ] [ j ] ; } } } function matrixAllOne ( set_bit ) { var p_arr = Array . from ( Array ( n ) , ( ) => Array ( n ) . fill ( 0 ) ) ; findPrefixCount ( p_arr , set_bit ) ; var ans = 0 ; for ( var j = 0 ; j < n ; j ++ ) { var i = n - 1 ; var q = [ ] ; var to_sum = 0 ; while ( i >= 0 ) { var c = 0 ; while ( q . length != 0 && q [ q . length - 1 ] [ 0 ] > p_arr [ i ] [ j ] ) { to_sum -= ( q [ q . length - 1 ] [ 1 ] + 1 ) * ( q [ q . length - 1 ] [ 0 ] - p_arr [ i ] [ j ] ) ; c += q [ q . length - 1 ] [ 1 ] + 1 ; q . pop ( ) ; } to_sum += p_arr [ i ] [ j ] ; ans += to_sum ; q . push ( [ p_arr [ i ] [ j ] , c ] ) ; i -- ; } } return ans ; } function sumAndMatrix ( arr ) { var sum = 0 ; var mul = 1 ; for ( var i = 0 ; i < 30 ; i ++ ) { var set_bit = Array . from ( Array ( n ) , ( ) => Array ( n ) ) ; for ( var R = 0 ; R < n ; R ++ ) for ( var C = 0 ; C < n ; C ++ ) set_bit [ R ] [ C ] = ( ( arr [ R ] [ C ] & ( 1 << i ) ) != 0 ) ; sum += ( mul * matrixAllOne ( set_bit ) ) ; mul *= 2 ; } return sum ; } var arr = [ [ 9 , 7 , 4 ] , [ 8 , 9 , 2 ] , [ 11 , 11 , 5 ] ] ; document . write ( sumAndMatrix ( arr ) ) ;