Smallest submatrix required to be removed such that sum of the remaining matrix is divisible by K | Function to find the length of the smallest subarray to be removed such that sum of elements is equal to S % K ; Remainder when total_sum is divided by K ; Stores curr_remainder and the most recent index at which curr_remainder has occured ; Stores required answer ; Add current element to curr_sum and take mod ; Update current remainder index ; If mod already exists in map the subarray exists ; Update res ; If not possible ; Return the result ; Function to find the smallest submatrix rqured to be deleted to make the sum of the matrix divisible by K ; Stores the sum of element of the matrix ; Traverse the matrix mat [ ] [ ] ; Update S ; Stores smallest area need to be deleted to get sum divisible by K ; Stores leftmost column of each matrix ; Stores rightmost column of each matrix ; Stores number of coulmns deleted of a matrix ; Store area of the deleted matrix ; prefixRowSum [ i ] : Store sum of sub matrix whose topmost left and bottommost right position is ( 0 , left ) ( i , right ) ; Iterate over all possible values of ( left , right ) ; Initialize all possible values of prefixRowSum [ ] to 0 ; Traverse each row from left to right column ; Update row_sum [ i ] ; ; Update width ; If no submatrix of the length ( right - left + 1 ) found to get the required output ; Update area ; If area is less than min_area ; Update min_area ; Driver Code ; Stores number of rows in the matrix ; Stores number of column in the matrix
function removeSmallestSubarray ( arr , S , n , k ) { var target_remainder = S % k ; var map1 = new Map ( ) ; map1 . set ( 0 , - 1 ) ; var curr_remainder = 0 ; var res = 1000000000 ; for ( var i = 0 ; i < n ; i ++ ) { curr_remainder = ( curr_remainder + arr [ i ] + k ) % k ; map1 . set ( curr_remainder , i ) ; var mod = ( curr_remainder - target_remainder + k ) % k ; if ( map1 . has ( mod ) ) { res = Math . min ( res , i - map1 . get ( mod ) ) ; } } if ( res == 1000000000 res == n ) { res = - 1 ; } return res ; } function smstSubmatDeleted ( mat , N , M , K ) { var S = 0 ; for ( var i = 0 ; i < N ; i ++ ) { for ( var j = 0 ; j < M ; j ++ ) S += mat [ i ] [ j ] ; } var min_area = N * M ; var left = 0 ; var right = 0 ; var width ; var area ; var prefixRowSum = Array ( N ) ; for ( left = 0 ; left < M ; left ++ ) { prefixRowSum = Array ( N ) . fill ( 0 ) ; for ( right = left ; right < M ; right ++ ) { for ( var i = 0 ; i < N ; i ++ ) { prefixRowSum [ i ] += mat [ i ] [ right ] ; } width = removeSmallestSubarray ( prefixRowSum , S , N , K ) ; if ( width != - 1 ) { area = ( right - left + 1 ) * ( width ) ; if ( area < min_area ) { min_area = area ; } } } } return min_area ; } var mat = [ [ 6 , 2 , 6 ] , [ 3 , 2 , 8 ] , [ 2 , 5 , 3 ] ] ; var K = 3 ; var N = mat . length ; var M = mat [ 0 ] . length ; document . write ( smstSubmatDeleted ( mat , N , M , K ) ) ;