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"
Solution 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 ) )