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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int sub_arrays ( int a [ ] , int n , int k ) { int sum [ n + 2 ] = { 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 ; map < int , int > mp ; for ( int i = 0 ; i < n + 1 ; i ++ ) { ans += mp [ sum [ i ] ] ; mp [ sum [ i ] ] ++ ; r ++ ; if ( r - l >= k ) { mp [ sum [ l ] ] -- ; l ++ ; } } return ans ; } int main ( ) { int a [ ] = { 1 , 4 , 2 , 3 , 5 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int k = 4 ; cout << sub_arrays ( a , n , k ) ; return 0 ; }