Find a subarray whose sum is divisible by size of the array | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void CheckSubarray ( int arr [ ] , int N ) { int presum [ N + 1 ] = { 0 } ; for ( int i = 1 ; i <= N ; i += 1 ) { presum [ i ] = presum [ i - 1 ] + arr [ i - 1 ] ; } vector < int > moduloclass [ N ] ; for ( int i = 1 ; i <= N ; i += 1 ) { moduloclass [ presum [ i ] % N ] . push_back ( i - 1 ) ; } if ( moduloclass [ 0 ] . size ( ) > 0 ) { cout << 0 << " ▁ " << moduloclass [ 0 ] [ 0 ] ; return ; } for ( int i = 1 ; i < N ; i += 1 ) { if ( moduloclass [ i ] . size ( ) >= 2 ) { cout << moduloclass [ i ] [ 0 ] + 1 << " ▁ " << moduloclass [ i ] [ 1 ] ; return ; } } } int main ( ) { int arr [ ] = { 7 , 3 , 5 , 2 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; CheckSubarray ( arr , N ) ; return 0 ; }