Count subarrays such that remainder after dividing sum of elements by K gives count of elements | C # implementation of the approach ; 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
using System ; using System . Collections . Generic ; class gfg { static int sub_arrays ( int [ ] a , int n , int k ) { int [ ] sum = new int [ n + 2 ] ; for ( int i = 0 ; i < n + 2 ; i ++ ) { sum [ i ] = 0 ; } for ( int i = 0 ; i < n ; i ++ ) { a [ i ] -- ; a [ i ] %= k ; sum [ i + 1 ] += sum [ i ] + a [ i ] ; sum [ i + 1 ] %= k ; } int ans = 0 , l = 0 , r = 0 ; Dictionary < int , int > mp = new Dictionary < int , int > ( ) ; for ( int i = 0 ; i < n + 1 ; i ++ ) { if ( ! mp . ContainsKey ( sum [ i ] ) ) mp . Add ( sum [ i ] , 0 ) ; } int temp ; for ( int i = 0 ; i < n + 1 ; i ++ ) { ans += ( int ) mp [ sum [ i ] ] ; temp = ( int ) mp [ sum [ i ] ] + 1 ; mp [ sum [ i ] ] = temp ; r ++ ; if ( r - l >= k ) { temp = ( int ) mp [ sum [ l ] ] - 1 ; mp [ sum [ i ] ] = temp ; l ++ ; } } return ans ; } public static void Main ( String [ ] args ) { int [ ] a = { 1 , 4 , 2 , 3 , 5 } ; int n = a . Length ; int k = 4 ; Console . Write ( sub_arrays ( a , n , k ) ) ; } }