Minimum number of 1 s present in a submatrix of given dimensions in a Binary Matrix | Python3 program for the above approach ; Function to count number of 1 s present in a sub matrix from ( start_i , start_j ) to ( end_i , end_j ) ; Stores the number of 1 s present in current submatrix ; Traverse the submatrix ; If mat [ x ] [ y ] is equal to 1 ; Increase count by 1 ; Return the total count of 1 s ; Function to find the minimum number of 1 s present in a sub - matrix of size A * B or B * A ; Stores the minimum count of 1 s ; Iterate i from 0 to N ; Iterate j from 0 to M ; If a valid sub matrix of size A * B from ( i , j ) is possible ; Count the number of 1 s present in the sub matrix of size A * B from ( i , j ) ; Update minimum if count is less than the current minimum ; If a valid sub matrix of size B * A from ( i , j ) is possible ; Count the number of 1 s in the sub matrix of size B * A from ( i , j ) ; Update minimum if count is less than the current minimum ; Return minimum as the final result ; Driver Code ; Given Input ; Function call to find the minimum number of 1 s in a submatrix of size A * B or B * A
P = 51 NEW_LINE def count1s ( start_i , start_j , end_i , end_j , mat ) : NEW_LINE INDENT count = 0 NEW_LINE for x in range ( start_i , end_i ) : NEW_LINE INDENT for y in range ( start_j , end_j ) : NEW_LINE INDENT if ( mat [ x ] [ y ] == 1 ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT def findMinimumCount ( N , M , A , B , mat ) : NEW_LINE INDENT minimum = 1e9 NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( M ) : NEW_LINE INDENT if ( i + A <= N and j + B <= M ) : NEW_LINE INDENT count = count1s ( i , j , i + A , j + B , mat ) NEW_LINE minimum = min ( count , minimum ) NEW_LINE DEDENT if ( i + B <= N and j + A <= M ) : NEW_LINE INDENT count = count1s ( i , j , i + B , j + A , mat ) NEW_LINE minimum = min ( count , minimum ) NEW_LINE DEDENT DEDENT DEDENT return minimum NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = 2 NEW_LINE B = 2 NEW_LINE N = 3 NEW_LINE M = 4 NEW_LINE mat = [ [ 1 , 0 , 1 , 0 ] , [ 0 , 1 , 0 , 1 ] , [ 1 , 0 , 1 , 0 ] ] NEW_LINE print ( findMinimumCount ( N , M , A , B , mat ) ) NEW_LINE DEDENT