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
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 for i in range ( 1 , N + 1 ) : NEW_LINE INDENT for j in range ( i , N + 1 ) : NEW_LINE INDENT if ( ( presum [ j ] - presum [ i - 1 ] ) % N == 0 ) : NEW_LINE INDENT print ( i - 1 , j - 1 ) NEW_LINE return NEW_LINE DEDENT DEDENT DEDENT print ( " - 1" ) NEW_LINE DEDENT arr = [ 7 , 5 , 3 , 7 ] NEW_LINE N = len ( arr ) NEW_LINE CheckSubarray ( arr , N ) NEW_LINE