Find a subarray whose sum is divisible by size of the array | C # implementation of the 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
using System ; using System . Collections . Generic ; 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 ] ; } List < int > [ ] moduloclass = new List < int > [ N ] ; for ( int i = 0 ; i < N ; i += 1 ) { moduloclass [ i ] = new List < int > ( ) ; } for ( int i = 1 ; i <= N ; i += 1 ) { moduloclass [ presum [ i ] % N ] . Add ( i - 1 ) ; } if ( moduloclass [ 0 ] . Count > 0 ) { Console . Write ( 0 + " ▁ " + moduloclass [ 0 ] [ 0 ] ) ; return ; } for ( int i = 1 ; i < N ; i += 1 ) { if ( moduloclass [ i ] . Count >= 2 ) { Console . Write ( moduloclass [ i ] [ 0 ] + 1 + " ▁ " + moduloclass [ i ] [ 1 ] ) ; return ; } } } public static void Main ( String [ ] args ) { int [ ] arr = { 7 , 3 , 5 , 2 } ; int N = arr . Length ; CheckSubarray ( arr , N ) ; } }