Count sub | Javascript implementation to count sub - matrices having sum divisible by the value ' k ' ; 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 program to test above
var SIZE = 10 ; function subCount ( arr , n , k ) { var mod = Array ( k ) . fill ( 0 ) ; var cumSum = 0 ; for ( var i = 0 ; i < n ; i ++ ) { cumSum += arr [ i ] ; mod [ ( ( cumSum % k ) + k ) % k ] ++ ; } var result = 0 ; for ( var 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 ) { var tot_count = 0 ; var left , right , i ; var temp = Array ( n ) ; for ( left = 0 ; left < n ; left ++ ) { temp = Array ( n ) . fill ( 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 ; } var mat = [ [ 5 , - 1 , 6 ] , [ - 2 , 3 , 8 ] , [ 7 , 4 , - 9 ] ] ; var n = 3 , k = 4 ; document . write ( " " + countSubmatrix ( mat , n , k ) ) ;