human
Count of square submatrices with average at least K | Function to count submatrixes with average greater than or equals to K.
Stores count of submatrices.
Stores the prefix sum of matrix.
Iterate over the range [ 1 , N ].
Iterate over the range [ 1 , M ].
Update the prefix sum.
Iterate over the range [ 1 , N ].
Iterate over the range [ 1 , M ].
Iterate until l and r are greater than 0.
Update count.
Stores sum of submatrix with bottom right corner as ( i , j ) and top left corner as ( l , r ).
If sum1 is less than or equal to sum2.
Increment cnt by 1.
Return cnt as the answer.
Driver Code.
Given Input.
Function Call"
How can the above be solved in Python?
assistant
#Here is code to count of square submatrices with average at least K and the other steps required.
 def cntMatrices ( arr , N , M , K ) :
	cnt = 0
	pre = [ [ 0 for i in range ( M + 1 ) ] for i in range ( N + 1 ) ]
	for i in range ( 1 , N + 1 ) :
		for j in range ( 1 , M + 1 ) :
			pre [ i ] [ j ] = ( arr [ i - 1 ] [ j - 1 ] + pre [ i - 1 ] [ j ] + pre [ i ] [ j - 1 ] - pre [ i - 1 ] [ j - 1 ] )
	for i in range ( 1 , N + 1 ) :
		for j in range ( 1 , M + 1 ) :
			l , r = i , j
			while l > 0 and r > 0 :
				sum1 = ( K * ( i - l + 1 ) * ( i - r + 1 ) )
				sum2 = ( pre [ i ] [ j ] - pre [ l - 1 ] [ r ] - pre [ l ] [ r - 1 ] + pre [ l - 1 ] [ r - 1 ] )
				if ( sum1 <= sum2 ) :
					cnt += 1
				l -= 1
				r -= 1
	return cnt
if __name__ == ' _ _ main _ _ ' :
	arr = [ [ 2 , 2 , 3 ] , [ 3 , 4 , 5 ] , [ 4 , 5 , 5 ] ]
	K = 4
	N = len ( arr )
	M = len ( arr [ 0 ] )
	print ( cntMatrices ( arr , N , M , K ) )