Divide array into two parts with equal sum according to the given constraints | Function that checks if the given conditions are satisfied ; To store the prefix sum of the array elements ; Sort the array ; Compute the prefix sum array ; Maximum element in the array ; Variable to check if there exists any number ; Stores the index of the largest number present in the array smaller than i ; Stores the index of the smallest number present in the array greater than i ; Find index of smallest number greater than i ; Find index of smallest number greater than i ; If there exists a number ; If no such number exists print no ; Driver code
def IfExists ( arr , n ) : NEW_LINE INDENT sum = [ 0 ] * n ; NEW_LINE arr . sort ( ) ; NEW_LINE sum [ 0 ] = arr [ 0 ] ; NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT sum [ i ] = sum [ i - 1 ] + arr [ i ] ; NEW_LINE DEDENT max = arr [ n - 1 ] ; NEW_LINE flag = False ; NEW_LINE for i in range ( 1 , max + 1 ) : NEW_LINE INDENT findex = 0 ; NEW_LINE lindex = 0 ; NEW_LINE l = 0 ; NEW_LINE r = n - 1 ; NEW_LINE while ( l <= r ) : NEW_LINE INDENT m = ( l + r ) // 2 ; NEW_LINE if ( arr [ m ] < i ) : NEW_LINE INDENT findex = m ; NEW_LINE l = m + 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT r = m - 1 ; NEW_LINE DEDENT DEDENT l = 1 ; NEW_LINE r = n ; NEW_LINE flag = False ; NEW_LINE while ( l <= r ) : NEW_LINE INDENT m = ( r + l ) // 2 ; NEW_LINE if ( arr [ m ] > i ) : NEW_LINE INDENT lindex = m ; NEW_LINE r = m - 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT l = m + 1 ; NEW_LINE DEDENT DEDENT if ( sum [ findex ] == sum [ n - 1 ] - sum [ lindex - 1 ] ) : NEW_LINE INDENT flag = True ; NEW_LINE break ; NEW_LINE DEDENT DEDENT if ( flag ) : NEW_LINE INDENT print ( " Yes " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 2 , 5 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE IfExists ( arr , n ) ; NEW_LINE DEDENT