Count subarrays having sum modulo K same as the length of the subarray | Java program for the above approach ; Function that counts the subarrays having sum modulo k equal to the length 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
import java . util . * ; import java . lang . * ; import java . io . * ; class GFG { static void countSubarrays ( int a [ ] , int n , int k ) { HashMap < Integer , Integer > cnt = new HashMap < > ( ) ; long ans = 0 ; ArrayList < Integer > pref = new ArrayList < > ( ) ; pref . add ( 0 ) ; for ( int i = 0 ; i < n ; i ++ ) pref . add ( ( a [ i ] + pref . get ( i ) ) % k ) ; cnt . put ( 0 , 1 ) ; for ( int i = 1 ; i <= n ; i ++ ) { int remIdx = i - k ; if ( remIdx >= 0 ) { if ( cnt . containsKey ( ( pref . get ( remIdx ) - remIdx % k + k ) % k ) ) cnt . put ( ( pref . get ( remIdx ) - remIdx % k + k ) % k , cnt . get ( ( pref . get ( remIdx ) - remIdx % k + k ) % k ) - 1 ) ; else cnt . put ( ( pref . get ( remIdx ) - remIdx % k + k ) % k , - 1 ) ; } if ( cnt . containsKey ( ( pref . get ( i ) - i % k + k ) % k ) ) ans += cnt . get ( ( pref . get ( i ) - i % k + k ) % k ) ; if ( cnt . containsKey ( ( pref . get ( i ) - i % k + k ) % k ) ) cnt . put ( ( pref . get ( i ) - i % k + k ) % k , cnt . get ( ( pref . get ( i ) - i % k + k ) % k ) + 1 ) ; else cnt . put ( ( pref . get ( i ) - i % k + k ) % k , 1 ) ; } System . out . println ( ans ) ; } public static void main ( String [ ] args ) throws java . lang . Exception { int arr [ ] = { 2 , 3 , 5 , 3 , 1 , 5 } ; int N = arr . length ; int K = 4 ; countSubarrays ( arr , N , K ) ; } }