Find a subarray whose sum is divisible by size of the array | Function to find 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 ; Generating all sub - arrays ; If the sum of the sub - array [ i : j ] is a multiple of N ; If the function reaches here it means there are no subarrays with sum as a multiple of N ; Driver code
function CheckSubarray ( arr , N ) { let presum = new Array ( N + 1 ) . fill ( 0 ) ; for ( let i = 1 ; i <= N ; i += 1 ) { presum [ i ] = presum [ i - 1 ] + arr [ i - 1 ] ; } for ( let i = 1 ; i <= N ; i += 1 ) { for ( let j = i ; j <= N ; j += 1 ) { if ( ( presum [ j ] - presum [ i - 1 ] ) % N == 0 ) { document . write ( ( i - 1 ) + " " + ( j - 1 ) ) ; return ; } } } document . write ( - 1 ) ; } let arr = [ 7 , 5 , 3 , 7 ] ; let N = arr . length ; CheckSubarray ( arr , N ) ;