Find a subarray whose sum is divisible by size of the array | 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
function CheckSubarray ( arr , N ) { let presum = new Array ( N + 1 ) ; for ( let i = 0 ; i < ( N + 1 ) ; i ++ ) presum [ i ] = 0 ; for ( let i = 1 ; i <= N ; i += 1 ) { presum [ i ] = presum [ i - 1 ] + arr [ i - 1 ] ; } let moduloclass = new Array ( N ) ; for ( let i = 0 ; i < N ; i += 1 ) { moduloclass [ i ] = [ ] ; } for ( let i = 1 ; i <= N ; i += 1 ) { moduloclass [ presum [ i ] % N ] . push ( i - 1 ) ; } if ( moduloclass [ 0 ] . length > 0 ) { document . write ( 0 + " " + moduloclass [ 0 ] [ 0 ] ) ; return ; } for ( let i = 1 ; i < N ; i += 1 ) { if ( moduloclass [ i ] . length >= 2 ) { document . write ( moduloclass [ i ] [ 0 ] + 1 + " " + moduloclass [ i ] [ 1 ] ) ; return ; } } } let arr = [ 7 , 3 , 5 , 2 ] ; let N = arr . length ; CheckSubarray ( arr , N ) ;