Minimize remaining array element by removing pairs and replacing them by their absolute difference | C ++ program to implement the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int smallestLeft ( int arr [ ] , int total , int sum , int i , vector < vector < int > > & dp ) { if ( i == 0 ) { return abs ( total - 2 * sum ) ; } if ( dp [ i ] [ sum ] != -1 ) return dp [ i ] [ sum ] ; int X = smallestLeft ( arr , total , sum + arr [ i - 1 ] , i - 1 , dp ) ; int Y = smallestLeft ( arr , total , sum , i - 1 , dp ) ; return dp [ i ] [ sum ] = min ( X , Y ) ; } int UtilSmallestElement ( int arr [ ] , int N ) { int total = 0 ; for ( int i = 0 ; i < N ; i ++ ) { total += arr [ i ] ; } vector < vector < int > > dp ( N + 1 , vector < int > ( total , -1 ) ) ; cout << smallestLeft ( arr , total , 0 , N , dp ) ; } int main ( ) { int arr [ ] = { 2 , 7 , 4 , 1 , 8 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; UtilSmallestElement ( arr , N ) ; return 0 ; }