Count subarrays such that remainder after dividing sum of elements by K gives count of elements | Function to return the number of subarrays of the given array such that the remainder when dividing the sum of its elements by K is equal to the number of its elements ; To store prefix sum ; We are dealing with zero indexed array ; Taking modulus value ; Prefix sum ; To store the required answer , the left index and the right index ; To store si - i value ; Include sum ; Increment the right index ; If subarray has at least k elements ; Return the required answer ; Driver code ; Function call
def sub_arrays ( a , n , k ) : NEW_LINE INDENT sum = [ 0 for i in range ( n + 2 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT a [ i ] -= 1 NEW_LINE a [ i ] %= k NEW_LINE sum [ i + 1 ] += sum [ i ] + a [ i ] NEW_LINE sum [ i + 1 ] %= k NEW_LINE DEDENT ans = 0 NEW_LINE l = 0 NEW_LINE r = 0 NEW_LINE mp = dict ( ) NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT if sum [ i ] in mp : NEW_LINE INDENT ans += mp [ sum [ i ] ] NEW_LINE DEDENT mp [ sum [ i ] ] = mp . get ( sum [ i ] , 0 ) + 1 NEW_LINE r += 1 NEW_LINE if ( r - l >= k ) : NEW_LINE INDENT mp [ sum [ l ] ] -= 1 NEW_LINE l += 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT a = [ 1 , 4 , 2 , 3 , 5 ] NEW_LINE n = len ( a ) NEW_LINE k = 4 NEW_LINE print ( sub_arrays ( a , n , k ) ) NEW_LINE