Remove element such that Array cannot be partitioned into two subsets with equal sum
Given an array arr[] of N size, the task is to remove an element such that the array cannot be partitioned into two groups with equal sum.
Note: If no element is required to remove, return -1.
Examples:
Input: arr[] = {4, 4, 8}, N = 3
Output: 4
Explanation: Two groups with equal sum are: G1 = {4, 4}, G2 = {8}.
If 8 is removed, then also two groups can be formed as: G1={4}, G2={4}.
So, 4 must be removed so that there will be no possible way to divide the remaining elements into 2 two groups having same sum.Input: arr[] ={6, 3, 9, 12}, N = 4
Output: 3
Approach: The problem can be solved by using Dynamic Programming approach based on the below observation:
Suppose the total sum is sum. Find if there is any division possible such that each group has subset sum as sum/2. If possible then find removing which element will satisfy the condition.
Follow the steps mentioned below to solve the problem:
- Create a 2D array dp[][] of size (sum/2 + 1)*(N+1). such that every filled entry has the following property :
- If a subset of {arr[0], arr[1], ..arr[j-1]} has sum equal to i then dp[j][i] = true.
- Else dp[i][j] = false.
- Now, if dp[N+1][sum/2+1] is true, then iterate a loop over that row and find dp[N][(sum – arr[i]) / 2] = false, then return the element in that index.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int removeElement( int arr[], int N) { // Variable to store the sum // of the array int sum = 0; for ( int i = 0; i < N; i++) { sum += arr[i]; } // If sum is odd, // it is impossible to divide if (sum % 2 == 1) { return -1; } // Value needed to find whether // it have a subset or not int target = sum / 2; vector<vector< bool > > dp(N + 1, vector< bool >(target + 1)); // Initializing the first column with 0 for ( int i = 0; i <= N; i++) { dp[i][0] = 1; } // Fill the table in // bottom up manner for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= target; j++) { if (arr[i - 1] <= j) { dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]]; } else { dp[i][j] = dp[i - 1][j]; } } } // If the last element of last row // and column is true if (dp[N][target] == 1) { for ( int i = 0; i < N; i++) { if (arr[i] % 2 || dp[N][(sum - arr[i]) / 2] == 0) { return arr[i]; } } } // If no element is returned, return 0 return -1; } // Driver Code int main() { int arr[] = { 6, 3, 9, 12 }; int N = sizeof (arr) / sizeof (arr[0]); cout << removeElement(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; public class GFG { static int removeElement( int arr[], int N) { // Variable to store the sum // of the array int sum = 0 ; for ( int i = 0 ; i < N; i++) { sum += arr[i]; } // If sum is odd, // it is impossible to divide if (sum % 2 == 1 ) { return - 1 ; } // Value needed to find whether // it have a subset or not int target = sum / 2 ; boolean dp[][] = new boolean [N + 1 ][target + 1 ]; // Initializing the first column with 0 for ( int i = 0 ; i <= N; i++) { dp[i][ 0 ] = true ; } // Fill the table in // bottom up manner for ( int i = 1 ; i <= N; i++) { for ( int j = 1 ; j <= target; j++) { if (arr[i - 1 ] <= j) { dp[i][j] = dp[i - 1 ][j] || dp[i - 1 ][j - arr[i - 1 ]]; } else { dp[i][j] = dp[i - 1 ][j]; } } } // If the last element of last row // and column is true if (dp[N][target] == true ) { for ( int i = 0 ; i < N; i++) { if (arr[i] % 2 == 1 || dp[N][(sum - arr[i]) / 2 ] == false ) { return arr[i]; } } } // If no element is returned, return 0 return - 1 ; } // Driver Code public static void main(String args[]) { int arr[] = { 6 , 3 , 9 , 12 }; int N = arr.length; System.out.println(removeElement(arr, N)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python3 program to implement # the above approach # Function to remove the element def removeElement(arr, N): # variable to store the sum of the array sums = 0 for i in range (N): sums + = arr[i] # if sum is odd, it is impossible # to divide if sums % 2 = = 1 : return - 1 # value reqd to find whether it has # a subset or not target = sums / / 2 dp = [] for i in range (N + 1 ): l1 = [ False ] * (target + 1 ) dp.append(l1) # initializing the first column for i in range (N + 1 ): dp[i][ 0 ] = 1 # fill the table in the # bottom up manner for i in range ( 1 , N + 1 ): for j in range ( 1 , target + 1 ): if arr[i - 1 ] < = j: dp[i][j] = dp[i - 1 ][j] | dp[i - 1 ][j - arr[i - 1 ]] else : dp[i][j] = dp[i - 1 ][j] # if the last element of last row # and column is true if dp[N][target] = = 1 : for i in range (N): if (arr[i] % 2 ) or dp[N][(sums - arr[i]) / / 2 ] = = 0 : return arr[i] # if no element is returned, return 0 return - 1 # Driver Code arr = [ 6 , 3 , 9 , 12 ] N = len (arr) print (removeElement(arr, N)) # This code is contributed by phasing17 |
C#
// C# program for the above approach using System; public class GFG{ static int removeElement( int [] arr, int N) { // Variable to store the sum // of the array int sum = 0; for ( int i = 0; i < N; i++) { sum += arr[i]; } // If sum is odd, // it is impossible to divide if (sum % 2 == 1) { return -1; } // Value needed to find whether // it have a subset or not int target = sum / 2; bool [,] dp = new bool [N + 1, target + 1]; // Initializing the first column with 0 for ( int i = 0; i <= N; i++) { dp[i, 0] = true ; } // Fill the table in // bottom up manner for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= target; j++) { if (arr[i - 1] <= j) { dp[i, j] = dp[i - 1, j] || dp[i - 1, j - arr[i - 1]]; } else { dp[i, j] = dp[i - 1, j]; } } } // If the last element of last row // and column is true if (dp[N, target] == true ) { for ( int i = 0; i < N; i++) { if (arr[i] % 2 == 1 || dp[N, (sum - arr[i]) / 2] == false ) { return arr[i]; } } } // If no element is returned, return 0 return -1; } // Driver Code static public void Main (){ int [] arr = { 6, 3, 9, 12 }; int N = arr.Length; Console.Write(removeElement(arr, N)); } } // This code is contributed by hrithikgarg03188. |
Javascript
<script> function removeElement( arr,N) { // Variable to store the sum // of the array let sum = 0; for (let i = 0; i < N; i++) { sum += arr[i]; } // If sum is odd, // it is impossible to divide if (sum % 2 == 1) { return -1; } // Value needed to find whether // it have a subset or not let target = Math.floor(sum / 2); let dp = new Array(N + 1) for (let i=0;i<dp.length;i++) { dp[i] = new Array(target+1) } // Initializing the first column with 0 for (let i = 0; i <= N; i++) { dp[i][0] = 1; } // Fill the table in // bottom up manner for (let i = 1; i <= N; i++) { for (let j = 1; j <= target; j++) { if (arr[i - 1] <= j) { dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]]; } else { dp[i][j] = dp[i - 1][j]; } } } // If the last element of last row // and column is true if (dp[N][target] == 1) { for (let i = 0; i < N; i++) { if (arr[i] % 2 || dp[N][(sum - arr[i]) / 2] == 0) { return arr[i]; } } } // If no element is returned, return 0 return -1; } // Driver Code let arr = [6, 3, 9, 12]; let N = arr.length; document.write(removeElement(arr, N)); // This code is contributed by lokeshpotta20. </script> |
3
Time Complexity: O(sum*N)
Auxiliary Space: O(sum*N)
Contact Us