Find a subarray whose sum is divisible by size of the array | Java implementation of above approach ; 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
import java . io . * ; 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 ] ; } for ( int i = 1 ; i <= N ; i += 1 ) { for ( int j = i ; j <= N ; j += 1 ) { if ( ( presum [ j ] - presum [ i - 1 ] ) % N == 0 ) { System . out . print ( ( i - 1 ) + " ▁ " + ( j - 1 ) ) ; return ; } } } System . out . print ( - 1 ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 7 , 5 , 3 , 7 } ; int N = arr . length ; CheckSubarray ( arr , N ) ; } }