Find a subarray whose sum is divisible by size of the array | Java implementation of above approach ; Function to check is there exists a subarray whose sum is a multiple of N ; Prefix sum array to store cumulative sum ; Single state dynamic programming relation for prefix sum array ; Modulo class vector ; Storing the index value in the modulo class vector ; If there exists a sub - array with starting index equal to zero ; In this class , there are more than two presums % N . Hence difference of any two subarrays would be a multiple of N ; 0 based indexing ; Driver code
import java . util . * ; class GFG { static void CheckSubarray ( int arr [ ] , int N ) { int [ ] presum = new int [ N + 1 ] ; for ( int i = 1 ; i <= N ; i += 1 ) { presum [ i ] = presum [ i - 1 ] + arr [ i - 1 ] ; } Vector < Integer > [ ] moduloclass = new Vector [ N ] ; for ( int i = 0 ; i < N ; i += 1 ) { moduloclass [ i ] = new Vector < > ( ) ; } for ( int i = 1 ; i <= N ; i += 1 ) { moduloclass [ presum [ i ] % N ] . add ( i - 1 ) ; } if ( moduloclass [ 0 ] . size ( ) > 0 ) { System . out . print ( 0 + " ▁ " + moduloclass [ 0 ] . get ( 0 ) ) ; return ; } for ( int i = 1 ; i < N ; i += 1 ) { if ( moduloclass [ i ] . size ( ) >= 2 ) { System . out . print ( moduloclass [ i ] . get ( 0 ) + 1 + " ▁ " + moduloclass [ i ] . get ( 1 ) ) ; return ; } } } public static void main ( String args [ ] ) { int arr [ ] = { 7 , 3 , 5 , 2 } ; int N = arr . length ; CheckSubarray ( arr , N ) ; } }