Minimize remaining array element by removing pairs and replacing them by their absolute difference | Java program to implement the above approach ; Function to find minimize the remaining array element by removing pairs and replacing them by their absolute difference ; Stores sum of array elements ; Traverse the array ; Update totalSum ; Stores half of totalSum ; dp [ i ] : True if sum i can be obtained as a subset sum ; Base case ; Stores closest sum that can be obtained as a subset sum ; Traverse the array ; Iterate over all possible value of sum ; Update dp [ j ] ; If sum i can be obtained from array elements ; Update reach ; Driver Code
import java . util . * ; class GFG { static int SmallestElementLeft ( int arr [ ] , int N ) { int totalSum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { totalSum += arr [ i ] ; } int req = totalSum / 2 ; boolean [ ] dp = new boolean [ req + 1 ] ; Arrays . fill ( dp , false ) ; dp [ 0 ] = true ; int reach = 0 ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = req ; j - arr [ i ] >= 0 ; j -- ) { dp [ j ] = dp [ j ] || dp [ j - arr [ i ] ] ; if ( dp [ j ] ) { reach = Math . max ( reach , j ) ; } } } return totalSum - ( 2 * reach ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 2 , 2 } ; int N = arr . length ; System . out . print ( SmallestElementLeft ( arr , N ) ) ; } }