text: Count subarrays having sum modulo K same as the length of the subarray | C # program for the above approach ; Function that counts the subarrays having sum modulo k equal to the length of subarray ; Stores the count of ( pref [ i ] - i ) % k ; Stores the count of subarray ; Stores prefix sum of the array ; Find prefix sum array ; Base Condition ; Remove the index at present after K indices from the current index ; Update the answer for subarrays ending at the i - th index ; Add the calculated value of current index to count ; Print the count of subarrays ; Driver Code ; Given [ ] arr ; Size of the array ; Given K ; Function call
code: using System ; using System . Collections . Generic ; class GFG { static void countSubarrays ( int [ ] a , int n , int k ) { Dictionary < int , int > cnt = new Dictionary < int , int > ( ) ; long ans = 0 ; List < int > pref = new List < int > ( ) ; pref . Add ( 0 ) ; for ( int i = 0 ; i < n ; i ++ ) pref . Add ( ( a [ i ] + pref [ i ] ) % k ) ; cnt . Add ( 0 , 1 ) ; for ( int i = 1 ; i <= n ; i ++ ) { int remIdx = i - k ; if ( remIdx >= 0 ) { if ( cnt . ContainsKey ( ( pref [ remIdx ] - remIdx % k + k ) % k ) ) cnt [ ( pref [ remIdx ] - remIdx % k + k ) % k ] = cnt [ ( pref [ remIdx ] - remIdx % k + k ) % k ] - 1 ; else cnt . Add ( ( pref [ remIdx ] - remIdx % k + k ) % k , - 1 ) ; } if ( cnt . ContainsKey ( ( pref [ i ] - i % k + k ) % k ) ) ans += cnt [ ( pref [ i ] - i % k + k ) % k ] ; if ( cnt . ContainsKey ( ( pref [ i ] - i % k + k ) % k ) ) cnt [ ( pref [ i ] - i % k + k ) % k ] = cnt [ ( pref [ i ] - i % k + k ) % k ] + 1 ; else cnt . Add ( ( pref [ i ] - i % k + k ) % k , 1 ) ; } Console . WriteLine ( ans ) ; } public static void Main ( String [ ] args ) { int [ ] arr = { 2 , 3 , 5 , 3 , 1 , 5 } ; int N = arr . Length ; int K = 4 ; countSubarrays ( arr , N , K ) ; } }