Minimize remaining array element by removing pairs and replacing them by their absolute difference | function to find the smallest element left in the array by the given operations ; Base Case ; If this subproblem has occurred previously ; Including i - th array element into the first subset ; If i - th array element is not selected ; Update dp [ i ] [ sum ] ; Utility function to find smallest element left in the array by the given operations ; Stores sum of the array elements ; Traverse the array ; Update total ; Stores overlapping subproblems ; Driver Code
def smallestLeft ( arr , total , sum , i , dp ) : NEW_LINE INDENT if ( i == 0 ) : NEW_LINE INDENT return abs ( total - 2 * sum ) NEW_LINE DEDENT if ( dp [ i ] [ sum ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ sum ] NEW_LINE DEDENT X = smallestLeft ( arr , total , sum + arr [ i - 1 ] , i - 1 , dp ) NEW_LINE Y = smallestLeft ( arr , total , sum , i - 1 , dp ) NEW_LINE dp [ i ] [ sum ] = min ( X , Y ) NEW_LINE return dp [ i ] [ sum ] NEW_LINE DEDENT def UtilSmallestElement ( arr , N ) : NEW_LINE INDENT total = 0 NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT total += arr [ i ] NEW_LINE DEDENT dp = [ [ - 1 for y in range ( total ) ] for x in range ( N + 1 ) ] NEW_LINE print ( smallestLeft ( arr , total , 0 , N , dp ) ) NEW_LINE DEDENT arr = [ 2 , 7 , 4 , 1 , 8 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE UtilSmallestElement ( arr , N ) NEW_LINE