Count subarrays having sum modulo K same as the length of the subarray | Function that counts the subarrays s . t . sum of elements in the subarray modulo k is equal to size 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 ; Given arr [ ] ; Size of the array ; Given K ; Function call
def countSubarrays ( a , n , k ) : NEW_LINE INDENT cnt = { } NEW_LINE ans = 0 NEW_LINE pref = [ ] NEW_LINE pref . append ( 0 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT pref . append ( ( a [ i ] + pref [ i ] ) % k ) NEW_LINE DEDENT cnt [ 0 ] = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT remIdx = i - k NEW_LINE if ( remIdx >= 0 ) : NEW_LINE INDENT if ( ( pref [ remIdx ] - remIdx % k + k ) % k in cnt ) : NEW_LINE INDENT cnt [ ( pref [ remIdx ] - remIdx % k + k ) % k ] -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt [ ( pref [ remIdx ] - remIdx % k + k ) % k ] = - 1 NEW_LINE DEDENT DEDENT if ( pref [ i ] - i % k + k ) % k in cnt : NEW_LINE INDENT ans += cnt [ ( pref [ i ] - i % k + k ) % k ] NEW_LINE DEDENT if ( pref [ i ] - i % k + k ) % k in cnt : NEW_LINE INDENT cnt [ ( pref [ i ] - i % k + k ) % k ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt [ ( pref [ i ] - i % k + k ) % k ] = 1 NEW_LINE DEDENT DEDENT print ( ans , end = ' ▁ ' ) NEW_LINE DEDENT arr = [ 2 , 3 , 5 , 3 , 1 , 5 ] NEW_LINE N = len ( arr ) NEW_LINE K = 4 NEW_LINE countSubarrays ( arr , N , K ) NEW_LINE