Subarray whose absolute sum is closest to K | function to return the index ; Add Last element tp currSum ; Save Difference of previous Iteration ; Calculate new Difference ; When the Sum exceeds K ; Current Difference greater in magnitude Store Temporary Result ; Difference in Previous was lesser In previous , Right index = j - 1 ; In next iteration , Left Index Increases but Right Index remains the Same Update currSum and i Accordingly ; Case to simply increase Right Index ; Check if lesser deviation found ; Driver Code
def getSubArray ( arr , n , K ) : NEW_LINE INDENT currSum = 0 NEW_LINE prevDif = 0 NEW_LINE currDif = 0 NEW_LINE result = [ - 1 , - 1 , abs ( K - abs ( currSum ) ) ] NEW_LINE resultTmp = result NEW_LINE i = 0 NEW_LINE j = 0 NEW_LINE while ( i <= j and j < n ) : NEW_LINE INDENT currSum += arr [ j ] NEW_LINE prevDif = currDif NEW_LINE currDif = K - abs ( currSum ) NEW_LINE if ( currDif <= 0 ) : NEW_LINE INDENT if abs ( currDif ) < abs ( prevDif ) : NEW_LINE INDENT resultTmp = [ i , j , currDif ] NEW_LINE DEDENT else : NEW_LINE INDENT resultTmp = [ i , j - 1 , prevDif ] NEW_LINE DEDENT currSum -= ( arr [ i ] + arr [ j ] ) NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT resultTmp = [ i , j , currDif ] NEW_LINE j += 1 NEW_LINE DEDENT if ( abs ( resultTmp [ 2 ] ) < abs ( result [ 2 ] ) ) : NEW_LINE INDENT result = resultTmp NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT def main ( ) : NEW_LINE INDENT arr = [ 15 , - 3 , 5 , 2 , 7 , 6 , 34 , - 6 ] NEW_LINE n = len ( arr ) NEW_LINE K = 50 NEW_LINE [ i , j , minDev ] = getSubArray ( arr , n , K ) NEW_LINE if ( i == - 1 ) : NEW_LINE INDENT print ( " The ▁ empty ▁ array ▁ shows ▁ minimum ▁ Deviation " ) NEW_LINE return 0 NEW_LINE DEDENT for i in range ( i , j + 1 ) : NEW_LINE INDENT print arr [ i ] , NEW_LINE DEDENT DEDENT main ( ) NEW_LINE