Given an array arr[] consisting of N positive integers, the task is to minimize the remaining array element that can be obtained by repeatedly removing a pair of array elements and replacing them by their absolute difference.
Examples:
Input: arr[] ={ 2, 7, 4, 1, 8, 1 }
Output: 1
Explanation:
Removing the pair (arr[0], arr[2]) from arr[] and inserting abs(arr[0] – arr[2]) into arr[] modifies arr[] to { 2, 7, 1, 8, 1 }.
Removing the pair (arr[1], arr[3]) from arr[] and inserting abs(arr[1] – arr[3]) into arr[] modifies arr[] to { 2, 1, 1, 1 }.
Removing the pair (arr[0], arr[1]) from arr[] and inserting abs(arr[0] – arr[1]) into arr[] modifies arr[] to { 1, 1, 1 }.
Removing the pair (arr[0], arr[1]) from arr[] modifies arr[] to { 1 }.
Therefore, the required output is 1.Input: arr[] = { 1, 1, 4, 2, 2 }
Output: 0
Approach: The problem can be solved using Dynamic programming based on the following observations:
Consider an array arr[] = { a, b, c, d }.
If a > b, then removing the pair (a, b) modifies arr[] to { a – b, c, d }
If c > d, then removing the pair (c, d) modifies arr[] to { a – b, c – d }
If (a – b) > (c – d), then removing the pair (a – b, c – d) modifies arr[] to { (a + d) – (b + c) }
From the above observation, it can be observed that the problem is to partition the array into two subsets with minimum difference of their subset sums.
Following is the recurrence relation:
min_diff(i, sum) = min(min_diff(i – 1, sum + arr[i – 1]), min_diff(i – 1, sum))
where, i : index of array elements
sum : sum of elements of the first subset
Follow the steps below to solve the problem:
- Initialize a 2D array, say dp[][], to store the minimum difference of subset sums that can be obtained upto the ith element.
- Use the above recurrence relation and calculate the value of dp[N][sum].
- Finally, print the value of dp[N][sum] as the required sum.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the smallest element // left in the array by the given operations int smallestLeft( int arr[], int total, int sum, int i, vector<vector< int > > &dp) { // Base Case if (i == 0) { return abs (total - 2 * sum); } // If this subproblem // has occurred previously if (dp[i][sum] != -1) return dp[i][sum]; // Including i-th array element // into the first subset int X = smallestLeft(arr, total, sum + arr[i - 1], i - 1, dp); // If i-th array element is not selected int Y = smallestLeft(arr, total, sum, i - 1, dp); // Update dp[i][sum] return dp[i][sum] = min(X, Y); } // Utility function to find smallest element // left in the array by the given operations int UtilSmallestElement( int arr[], int N) { // Stores sum of // the array elements int total = 0; // Traverse the array for ( int i = 0; i < N; i++) { // Update total total += arr[i]; } // Stores overlapping // subproblems vector<vector< int > > dp(N + 1, vector< int >(total, -1)); cout<< smallestLeft(arr, total, 0, N, dp); } // Driver Code int main() { int arr[] = { 2, 7, 4, 1, 8, 1 }; int N = sizeof (arr) / sizeof (arr[0]); UtilSmallestElement(arr, N); return 0; } |
Java
// Java program for above approach import java.util.*; import java.lang.*; class GFG { // Function to find the smallest element // left in the array by the given operations static int smallestLeft( int arr[], int total, int sum, int i, int [][] dp) { // Base Case if (i == 0 ) { return Math.abs(total - 2 * sum); } // If this subproblem // has occurred previously if (dp[i][sum] != - 1 ) return dp[i][sum]; // Including i-th array element // into the first subset int X = smallestLeft(arr, total, sum + arr[i - 1 ], i - 1 , dp); // If i-th array element is not selected int Y = smallestLeft(arr, total, sum, i - 1 , dp); // Update dp[i][sum] return dp[i][sum] = Math.min(X, Y); } // Utility function to find smallest element // left in the array by the given operations static void UtilSmallestElement( int arr[], int N) { // Stores sum of // the array elements int total = 0 ; // Traverse the array for ( int i = 0 ; i < N; i++) { // Update total total += arr[i]; } // Stores overlapping // subproblems int [][] dp = new int [N + 1 ][total]; for ( int [] k:dp) Arrays.fill(k, - 1 ); System.out.println(smallestLeft(arr, total, 0 , N, dp)); } // Driver function public static void main (String[] args) { int arr[] = { 2 , 7 , 4 , 1 , 8 , 1 }; int N = arr.length; UtilSmallestElement(arr, N); } } // This code is contributed by offbeat |
Python3
# Python program to implement # the above approach # function to find the smallest element # left in the array by the given operations def smallestLeft( arr, total, sum , i, dp): # Base Case if (i = = 0 ): return abs (total - 2 * sum ) # If this subproblem # has occurred previously if (dp[i][ sum ] ! = - 1 ): return dp[i][ sum ] # Including i-th array element # into the first subset X = smallestLeft(arr, total, sum + arr[i - 1 ], i - 1 , dp) # If i-th array element is not selected Y = smallestLeft(arr, total, sum , i - 1 , dp) # Update dp[i][sum] dp[i][ sum ] = min (X, Y) return dp[i][ sum ] # Utility function to find smallest element # left in the array by the given operations def UtilSmallestElement(arr, N): # Stores sum of # the array elements total = 0 # Traverse the array for i in range ( 0 , N): # Update total total + = arr[i] # Stores overlapping # subproblems dp = [[ - 1 for y in range (total)] for x in range (N + 1 )] print (smallestLeft(arr, total, 0 , N, dp)) # Driver Code arr = [ 2 , 7 , 4 , 1 , 8 , 1 ] N = len (arr) UtilSmallestElement(arr, N) # This code is contributed by amreshkumar3. |
C#
// C# program for above approach using System; public class GFG { // Function to find the smallest element // left in the array by the given operations static int smallestLeft( int []arr, int total, int sum, int i, int [,] dp) { // Base Case if (i == 0) { return Math.Abs(total - 2 * sum); } // If this subproblem // has occurred previously if (dp[i,sum] != -1) return dp[i,sum]; // Including i-th array element // into the first subset int X = smallestLeft(arr, total, sum + arr[i - 1], i - 1, dp); // If i-th array element is not selected int Y = smallestLeft(arr, total, sum, i - 1, dp); // Update dp[i,sum] return dp[i,sum] = Math.Min(X, Y); } // Utility function to find smallest element // left in the array by the given operations static void UtilSmallestElement( int []arr, int N) { // Stores sum of // the array elements int total = 0; // Traverse the array for ( int i = 0; i < N; i++) { // Update total total += arr[i]; } // Stores overlapping // subproblems int [,] dp = new int [N + 1,total]; for ( int i = 0; i < N + 1; i++) { for ( int j = 0; j < total; j++) { dp[i, j] = -1; } } Console.WriteLine(smallestLeft(arr, total, 0, N, dp)); } // Driver function public static void Main(String[] args) { int []arr = { 2, 7, 4, 1, 8, 1 }; int N = arr.Length; UtilSmallestElement(arr, N); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // javascript program of the above approach let M = 6; let N = 7; // Function to find the smallest element // left in the array by the given operations function smallestLeft(arr, total, sum, i, dp) { // Base Case if (i == 0) { return Math.abs(total - 2 * sum); } // If this subproblem // has occurred previously if (dp[i][sum] != -1) return dp[i][sum]; // Including i-th array element // into the first subset let X = smallestLeft(arr, total, sum + arr[i - 1], i - 1, dp); // If i-th array element is not selected let Y = smallestLeft(arr, total, sum, i - 1, dp); // Update dp[i][sum] return dp[i][sum] = Math.min(X, Y); } // Utility function to find smallest element // left in the array by the given operations function UtilSmallestElement(arr, N) { // Stores sum of // the array elements let total = 0; // Traverse the array for (let i = 0; i < N; i++) { // Update total total += arr[i]; } // Stores overlapping // subproblems let dp = new Array(N + 1); // Loop to create 2D array using 1D array for ( var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } for ( var i = 0; i < dp.length; i++) { for ( var j = 0; j < dp.length; j++) { dp[i][j] = 1; } } document.write(smallestLeft(arr, total, 0, N, dp)); } // Driver Code let arr = [ 2, 7, 4, 1, 8, 1 ]; let n = arr.length; UtilSmallestElement(arr, n); // This code is contributed by target_2. </script> |
1
Time Complexity: O(N * sum), where sum is the sum of array elements
Auxiliary space: O(N * sum)
Space optimized Approach: To optimize the above approach, the idea is to use tabulation method. Follow the steps below to solve the problem:
- Initialize an array, say dp[], where dp[i] checks if the sum i can be obtained as the sum of a subset of the given array.
- Traverse the array and calculate the sum of array elements and store it in a variable, say totalSum.
- Using the above recurrence relation, find the closest value of (totalSum] / 2), say X, such that dp[X] is true.
- Finally, print the value of (totalSum – 2 * X).
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find minimize the remaining // array element by removing pairs and // replacing them by their absolute difference int SmallestElementLeft( int arr[], int N) { // Stores sum of array elements int totalSum = 0; // Traverse the array for ( int i = 0; i < N; i++) { // Update totalSum totalSum += arr[i]; } // Stores half of totalSum int req = totalSum / 2; // dp[i]: True if sum i can be // obtained as a subset sum bool dp[req + 1]; // Initialize dp[] array memset (dp, false , sizeof (dp)); // Base case dp[0] = true ; // Stores closest sum that can // be obtained as a subset sum int reach = 0; // Traverse the array for ( int i = 0; i < N; i++) { // Iterate over all possible value of sum for ( int j = req; j - arr[i] >= 0; j--) { // Update dp[j] dp[j] = dp[j] || dp[j - arr[i]]; // If sum i can be obtained // from array elements if (dp[j]) { // Update reach reach = max(reach, j); } } } return totalSum - (2 * reach); } // Driver Code int main() { int arr[] = { 2, 2, 2 }; int N = sizeof (arr) / sizeof (arr[0]); cout<< SmallestElementLeft(arr, N); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find minimize the remaining // array element by removing pairs and // replacing them by their absolute difference static int SmallestElementLeft( int arr[], int N) { // Stores sum of array elements int totalSum = 0 ; // Traverse the array for ( int i = 0 ; i < N; i++) { // Update totalSum totalSum += arr[i]; } // Stores half of totalSum int req = totalSum / 2 ; // dp[i]: True if sum i can be // obtained as a subset sum boolean [] dp = new boolean [req + 1 ]; // Initialize dp[] array Arrays.fill(dp, false ); // Base case dp[ 0 ] = true ; // Stores closest sum that can // be obtained as a subset sum int reach = 0 ; // Traverse the array for ( int i = 0 ; i < N; i++) { // Iterate over all possible value of sum for ( int j = req; j - arr[i] >= 0 ; j--) { // Update dp[j] dp[j] = dp[j] || dp[j - arr[i]]; // If sum i can be obtained // from array elements if (dp[j]) { // Update reach reach = Math.max(reach, j); } } } return totalSum - ( 2 * reach); } // Driver Code public static void main(String[] args) { int arr[] = { 2 , 2 , 2 }; int N = arr.length; System.out.print(SmallestElementLeft(arr, N)); } } // This code is contributed by code_hunt |
Python3
# Python3 program to implement # the above approach # Function to find minimize the remaining # array element by removing pairs and # replacing them by their absolute difference def SmallestElementLeft(arr, N): # Stores sum of array elements totalSum = 0 # Traverse the array for i in range (N): # Update totalSum totalSum + = arr[i] # Stores half of totalSum req = totalSum / / 2 # dp[i]: True if sum i can be # obtained as a subset sum dp = [ False for i in range (req + 1 )] # Initialize dp[] array # memset(dp, false, sizeof(dp)); # Base case dp[ 0 ] = True # Stores closest sum that can # be obtained as a subset sum reach = 0 # Traverse the array for i in range (N): # Iterate over all possible value of sum j = req while j> = arr[i]: # Update dp[j] dp[j] = dp[j] or dp[j - arr[i]] # If sum i can be obtained # from array elements if (dp[j]): # Update reach reach = max (reach, j) j - = 1 return totalSum - ( 2 * reach) # Driver Code if __name__ = = '__main__' : arr = [ 2 , 2 , 2 ] N = len (arr) print (SmallestElementLeft(arr, N)) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; class GFG { // Function to find minimize the remaining // array element by removing pairs and // replacing them by their absolute difference static int SmallestElementLeft( int [] arr, int N) { // Stores sum of array elements int totalSum = 0; // Traverse the array for ( int i = 0; i < N; i++) { // Update totalSum totalSum += arr[i]; } // Stores half of totalSum int req = totalSum / 2; // dp[i]: True if sum i can be // obtained as a subset sum bool [] dp = new bool [req + 1]; // Initialize dp[] array for ( int i = 0; i < req + 1; i++) { dp[i] = false ; } // Base case dp[0] = true ; // Stores closest sum that can // be obtained as a subset sum int reach = 0; // Traverse the array for ( int i = 0; i < N; i++) { // Iterate over all possible value of sum for ( int j = req; j - arr[i] >= 0; j--) { // Update dp[j] dp[j] = dp[j] || dp[j - arr[i]]; // If sum i can be obtained // from array elements if (dp[j]) { // Update reach reach = Math.Max(reach, j); } } } return totalSum - (2 * reach); } // Driver Code public static void Main() { int [] arr = { 2, 2, 2 }; int N = arr.Length; Console.Write(SmallestElementLeft(arr, N)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // Javascript program to implement // the above approach // Function to find minimize the remaining // array element by removing pairs and // replacing them by their absolute difference function SmallestElementLeft(arr , N) { // Stores sum of array elements var totalSum = 0; // Traverse the array for (i = 0; i < N; i++) { // Update totalSum totalSum += arr[i]; } // Stores half of totalSum var req = totalSum / 2; // dp[i]: True if sum i can be // obtained as a subset sum var dp =Array(req + 1).fill( false ); // Base case dp[0] = true ; // Stores closest sum that can // be obtained as a subset sum var reach = 0; // Traverse the array for (i = 0; i < N; i++) { // Iterate over all possible value of sum for (j = req; j - arr[i] >= 0; j--) { // Update dp[j] dp[j] = dp[j] || dp[j - arr[i]]; // If sum i can be obtained // from array elements if (dp[j]) { // Update reach reach = Math.max(reach, j); } } } return totalSum - (2 * reach); } // Driver Code var arr = [ 2, 2, 2 ]; var N = arr.length; document.write(SmallestElementLeft(arr, N)); // This code contributed by aashish1995 </script> |
Output:
2
Time Complexity: O(N * sum), where sum is the sum of array elements
Auxiliary space: O(sum)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!