Minimize remaining array element by removing pairs and replacing them by their absolute difference | Java program for 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 function
import java . util . * ; import java . lang . * ; class GFG { static int smallestLeft ( int arr [ ] , int total , int sum , int i , int [ ] [ ] dp ) { if ( i == 0 ) { return Math . 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 ] = Math . min ( X , Y ) ; } static void UtilSmallestElement ( int arr [ ] , int N ) { int total = 0 ; for ( int i = 0 ; i < N ; i ++ ) { total += arr [ i ] ; } int [ ] [ ] dp = new int [ N + 1 ] [ total ] ; for ( int [ ] k : dp ) Arrays . fill ( k , - 1 ) ; System . out . println ( smallestLeft ( arr , total , 0 , N , dp ) ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 7 , 4 , 1 , 8 , 1 } ; int N = arr . length ; UtilSmallestElement ( arr , N ) ; } }