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
def CheckSubarray ( arr , N ) : NEW_LINE INDENT presum = [ 0 for i in range ( N + 1 ) ] NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT presum [ i ] = presum [ i - 1 ] + arr [ i - 1 ] NEW_LINE DEDENT moduloclass = [ [ ] ] * N NEW_LINE for i in range ( 1 , N + 1 , 1 ) : NEW_LINE INDENT moduloclass [ presum [ i ] % N ] . append ( i - 1 ) NEW_LINE DEDENT if ( len ( moduloclass [ 0 ] ) > 0 ) : NEW_LINE INDENT print ( 0 + 1 , moduloclass [ 0 ] [ 0 ] + 2 ) NEW_LINE return NEW_LINE DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT if ( len ( moduloclass [ i ] ) >= 2 ) : NEW_LINE INDENT print ( moduloclass [ i ] [ 0 ] + 1 , moduloclass [ i ] [ 1 ] ) NEW_LINE return NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 7 , 3 , 5 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE CheckSubarray ( arr , N ) NEW_LINE DEDENT