text: Count subarrays having sum modulo K same as the length of the subarray | C ++ program of the above approach ; 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 ; Driver Code ; Given arr [ ] ; Size of the array ; Given K ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; long long int countSubarrays ( int a [ ] , int n , int k ) { unordered_map < int , int > cnt ; long long int ans = 0 ; vector < int > pref ; pref . push_back ( 0 ) ; for ( int i = 0 ; i < n ; i ++ ) pref . push_back ( ( a [ i ] + pref [ i ] ) % k ) ; cnt [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { int remIdx = i - k ; if ( remIdx >= 0 ) { cnt [ ( pref [ remIdx ] - remIdx % k + k ) % k ] -- ; } ans += cnt [ ( pref [ i ] - i % k + k ) % k ] ; cnt [ ( pref [ i ] - i % k + k ) % k ] ++ ; } cout << ans << ' ▁ ' ; } int main ( ) { int arr [ ] = { 2 , 3 , 5 , 3 , 1 , 5 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int K = 4 ; countSubarrays ( arr , N , K ) ; return 0 ; }