Smallest submatrix required to be removed such that sum of the remaining matrix is divisible by K | Python3 program to implement the above approach ; 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
import sys NEW_LINE def removeSmallestSubarray ( arr , S , n , k ) : NEW_LINE INDENT target_remainder = S % k NEW_LINE map1 = { } NEW_LINE map1 [ 0 ] = - 1 NEW_LINE curr_remainder = 0 NEW_LINE res = sys . maxsize NEW_LINE for i in range ( n ) : NEW_LINE INDENT curr_remainder = ( curr_remainder + arr [ i ] + k ) % k NEW_LINE map1 [ curr_remainder ] = i NEW_LINE mod = ( curr_remainder - target_remainder + k ) % k NEW_LINE if ( mod in map1 ) : NEW_LINE INDENT res = min ( res , i - map1 [ mod ] ) NEW_LINE DEDENT DEDENT if ( res == sys . maxsize or res == n ) : NEW_LINE INDENT res = - 1 NEW_LINE DEDENT return res NEW_LINE DEDENT def smstSubmatDeleted ( mat , N , M , K ) : NEW_LINE INDENT S = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( M ) : NEW_LINE INDENT S += mat [ i ] [ j ] NEW_LINE DEDENT DEDENT min_area = N * M NEW_LINE left = 0 NEW_LINE right = 0 NEW_LINE width = 0 NEW_LINE area = 0 NEW_LINE prefixRowSm = [ 0 ] * N NEW_LINE for left in range ( M ) : NEW_LINE INDENT prefixRowSum = [ 0 ] * N NEW_LINE for right in range ( left , M ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT prefixRowSum [ i ] += mat [ i ] [ right ] NEW_LINE DEDENT width = removeSmallestSubarray ( prefixRowSum , S , N , K ) NEW_LINE if ( width != - 1 ) : NEW_LINE INDENT area = ( right - left + 1 ) * ( width ) NEW_LINE if ( area < min_area ) : NEW_LINE INDENT min_area = area NEW_LINE DEDENT DEDENT DEDENT DEDENT return min_area NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 6 , 2 , 6 ] , [ 3 , 2 , 8 ] , [ 2 , 5 , 3 ] ] NEW_LINE K = 3 NEW_LINE N = len ( mat ) NEW_LINE M = len ( mat [ 0 ] ) NEW_LINE print ( smstSubmatDeleted ( mat , N , M , K ) ) NEW_LINE DEDENT