Count of submatrix with sum X in a given Matrix | Java program for the above approach ; Size of a column ; Function to find the count of submatrix whose sum is X ; Copying arr to dp and making it indexed 1 ; Precalculate and store the sum of all rectangles with upper left corner at ( 0 , 0 ) ; ; Calculating sum in a 2d grid ; Stores the answer ; Minimum length of square ; Maximum length of square ; Flag to set if sub - square with sum X is found ; Calculate lower right index if upper right corner is at { i , j } ; Calculate the sum of elements in the submatrix with upper left column { i , j } and lower right column at { ni , nj } ; ; If sum X is found ; If sum > X , then size of the square with sum X must be less than mid ; If sum < X , then size of the square with sum X must be greater than mid ; If found , increment count by 1 ; ; Driver Code ; Given Matrix arr [ ] [ ] ; Function Call
import java . util . * ; class GFG { static final int m = 5 ; static int countSubsquare ( int arr [ ] [ ] , int n , int X ) { int [ ] [ ] dp = new int [ n + 1 ] [ m + 1 ] ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { dp [ i + 1 ] [ j + 1 ] = arr [ i ] [ j ] ; } } for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= m ; j ++ ) { dp [ i ] [ j ] += dp [ i - 1 ] [ j ] + dp [ i ] [ j - 1 ] - dp [ i - 1 ] [ j - 1 ] ; } } int cnt = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= m ; j ++ ) { int lo = 1 ; int hi = Math . min ( n - i , m - j ) + 1 ; boolean found = false ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; int ni = i + mid - 1 ; int nj = j + mid - 1 ; int sum = dp [ ni ] [ nj ] - dp [ ni ] [ j - 1 ] - dp [ i - 1 ] [ nj ] + dp [ i - 1 ] [ j - 1 ] ; if ( sum >= X ) { if ( sum == X ) { found = true ; } hi = mid - 1 ; } else { lo = mid + 1 ; } } if ( found == true ) { cnt ++ ; } } } return cnt ; } public static void main ( String [ ] args ) { int N = 4 , X = 10 ; int arr [ ] [ ] = { { 2 , 4 , 3 , 2 , 10 } , { 3 , 1 , 1 , 1 , 5 } , { 1 , 1 , 2 , 1 , 4 } , { 2 , 1 , 1 , 1 , 3 } } ; System . out . print ( countSubsquare ( arr , N , X ) + "NEW_LINE"); } }