Count sub | function to count all sub - arrays divisible by k ; create auxiliary hash array to count frequency of remainders ; Traverse original array and compute cumulative sum take remainder of this current cumulative sum and increase count by 1 for this remainder in mod array ; as the sum can be negative , taking modulo twice ; Initialize result ; Traverse mod ; If there are more than one prefix subarrays with a particular mod value . ; add the subarrays starting from the arr [ i ] which are divisible by k itself ; function to count all sub - matrices having sum divisible by the value ' k ' ; Variable to store the final output ; Set the left column ; Initialize all elements of temp as 0 ; Set the right column for the left column set by outer loop ; Calculate sum between current left and right for every row ' i ' ; Count number of subarrays in temp having sum divisible by ' k ' and then add it to ' tot _ count ' ; required count of sub - matrices having sum divisible by ' k ' ; Driver Code
< ? php function subCount ( $ arr , $ n , $ k ) { $ mod = array ( ) ; for ( $ i = 0 ; $ i < $ k ; $ i ++ ) $ mod [ $ i ] = 0 ; $ cumSum = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ cumSum += $ arr [ $ i ] ; $ mod [ ( ( $ cumSum % $ k ) + $ k ) % $ k ] ++ ; } $ result = 0 ; for ( $ i = 0 ; $ i < $ k ; $ i ++ ) if ( $ mod [ $ i ] > 1 ) $ result += ( $ mod [ $ i ] * ( $ mod [ $ i ] - 1 ) ) / 2 ; $ result += $ mod [ 0 ] ; return $ result ; } function countSubmatrix ( $ mat , $ n , $ k ) { $ tot_count = 0 ; $ temp = array ( ) ; for ( $ left = 0 ; $ left < $ n ; $ left ++ ) { for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ temp [ $ i ] = 0 ; for ( $ right = $ left ; $ right < $ n ; $ right ++ ) { for ( $ i = 0 ; $ i < $ n ; ++ $ i ) $ temp [ $ i ] += $ mat [ $ i ] [ $ right ] ; $ tot_count += subCount ( $ temp , $ n , $ k ) ; } } return $ tot_count ; } $ mat = array ( array ( 5 , -1 , 6 ) , array ( -2 , 3 , 8 ) , array ( 7 , 4 , -9 ) ) ; $ n = 3 ; $ k = 4 ; echo ( " Count ▁ = ▁ " . countSubmatrix ( $ mat , $ n , $ k ) ) ; ? >