Given an array arr[] consisting of N integers, the task is to minimize the count of elements required to be multiplied by -1 such that the sum of array elements is 0. If it is not possible to make the sum 0, print “-1”.
Examples:
Input: arr[] = {2, 3, 1, 4}
Output: 2
Explanation:
Multiply arr[0] by -1. Therefore, the array modifies to {-2, 3, 1, 4}.
Multiply arr[1] by -1. Therefore, the array modifies to {-2, -3, 1, 4}
Therefore, the sum of the modified array is 0 and the minimum operations required is 2.Input: arr[] = {2}
Output: -1
Naive Approach: The simplest approach is to divide the array into two subsets in every possible way. For each division, check if the difference of their subset-sum is 0 or not. If found to be 0, then the length of the smaller subset is the result.
Time Complexity: O(2N)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to use Dynamic Programming. Follow the steps to solve the problem:
- To make the sum of all array elements equal to 0, divide the given array elements into two subsets having an equal sum.
- Out of all the subsets possible of the given array, the subset whose size is the minimum of all is chosen.
- If the sum of the given array is odd, no subset is possible to make the sum 0, hence return -1
- Else, try all possible subset sums of the array and check if the sum of the subset is equal to sum/2. where the sum is the sum of all elements of the array.
- The recurrence relation of dp[] is:
dp(i, j) = min (dp(i+1, j – arr[i]]+1), dp(i+1, j))
where
dp (i, j) represents the minimum operations to make sum j equal to 0 using elements having index [i, N-1].
j represents the current sum.
i represents the current index.
- Using the above recurrence, print dp(0, sum/2) as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Initialize dp[][]int dp[2001][2001];// Function to find the minimum number// of operations to make sum of A[] 0int solve(vector<int>& A, int i, int sum, int N){ // Initialize answer int res = 2001; // Base case if (sum < 0 or (i == N and sum != 0)) { return 2001; } // Otherwise, return 0 if (sum == 0 or i >= N) { return dp[i][sum] = 0; } // Pre-computed subproblem if (dp[i][sum] != -1) { return dp[i][sum]; } // Recurrence relation for finding // the minimum of the sum of subsets res = min(solve(A, i + 1, sum - A[i], N) + 1, solve(A, i + 1, sum, N)); // Return the result return dp[i][sum] = res;}// Function to find the minimum number// of elements required to be flipped// to make sum the array equal to 0void minOp(vector<int>& A, int N){ int sum = 0; // Find the sum of array for (auto it : A) { sum += it; } if (sum % 2 == 0) { // Initialise dp[][] with -1 memset(dp, -1, sizeof(dp)); int ans = solve(A, 0, sum / 2, N); // No solution exists if (ans < 0 || ans > N) { cout << "-1" << endl; } // Otherwise else { cout << ans << endl; } } // If sum is odd, no // subset is possible else { cout << "-1" << endl; }}// Driver Codeint main(){ vector<int> A = { 2, 3, 1, 4 }; int N = A.size(); // Function Call minOp(A, N); return 0;} |
Java
// Java program for the above approachclass GFG{// Initialize dp[][]static int [][]dp = new int[2001][2001];// Function to find the minimum number// of operations to make sum of A[] 0static int solve(int []A, int i, int sum, int N){ // Initialize answer int res = 2001; // Base case if (sum < 0 || (i == N && sum != 0)) { return 2001; } // Otherwise, return 0 if (sum == 0 || i >= N) { return dp[i][sum] = 0; } // Pre-computed subproblem if (dp[i][sum] != -1) { return dp[i][sum]; } // Recurrence relation for finding // the minimum of the sum of subsets res = Math.min(solve(A, i + 1, sum - A[i], N) + 1, solve(A, i + 1, sum, N)); // Return the result return dp[i][sum] = res;}// Function to find the minimum number// of elements required to be flipped// to make sum the array equal to 0static void minOp(int []A, int N){ int sum = 0; // Find the sum of array for (int it : A) { sum += it; } if (sum % 2 == 0) { // Initialise dp[][] with -1 for(int i = 0; i < 2001; i++) { for (int j = 0; j < 2001; j++) { dp[i][j] = -1; } } int ans = solve(A, 0, sum / 2, N); // No solution exists if (ans < 0 || ans > N) { System.out.print("-1" +"\n"); } // Otherwise else { System.out.print(ans +"\n"); } } // If sum is odd, no // subset is possible else { System.out.print("-1" +"\n"); }}// Driver Codepublic static void main(String[] args){ int []A = { 2, 3, 1, 4 }; int N = A.length; // Function Call minOp(A, N);}}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Initialize dp[][]dp = [[-1 for i in range(2001)] for j in range(2001)]# Function to find the minimum number# of operations to make sum of A[] 0def solve(A, i, sum, N): # Initialize answer res = 2001 # Base case if (sum < 0 or (i == N and sum != 0)): return 2001 # Otherwise, return 0 if (sum == 0 or i >= N): dp[i][sum] = 0 return 0 # Pre-computed subproblem if (dp[i][sum] != -1): return dp[i][sum] # Recurrence relation for finding # the minimum of the sum of subsets res = min(solve(A, i + 1, sum - A[i], N) + 1, solve(A, i + 1, sum, N)) # Return the result dp[i][sum] = res return res# Function to find the minimum number# of elements required to be flipped# to make sum the array equal to 0def minOp(A, N): sum = 0 # Find the sum of array for it in A: sum += it if (sum % 2 == 0): # Initialise dp[][] with -1 dp = [[-1 for i in range(2001)] for j in range(2001)] ans = solve(A, 0, sum // 2, N) # No solution exists if (ans < 0 or ans > N): print("-1") # Otherwise else: print(ans) # If sum is odd, no # subset is possible else: print(-1)# Driver CodeA = [ 2, 3, 1, 4 ]N = len(A)# Function CallminOp(A, N)# This code is contributed by rohitsingh07052. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{// Initialize [,]dpstatic int [,]dp = new int[2001,2001];// Function to find the minimum number// of operations to make sum of []A 0static int solve(int []A, int i, int sum, int N){ // Initialize answer int res = 2001; // Base case if (sum < 0 || (i == N && sum != 0)) { return 2001; } // Otherwise, return 0 if (sum == 0 || i >= N) { return dp[i, sum] = 0; } // Pre-computed subproblem if (dp[i, sum] != -1) { return dp[i, sum]; } // Recurrence relation for finding // the minimum of the sum of subsets res = Math.Min(solve(A, i + 1, sum - A[i], N) + 1, solve(A, i + 1, sum, N)); // Return the result return dp[i, sum] = res;}// Function to find the minimum number// of elements required to be flipped// to make sum the array equal to 0static void minOp(int []A, int N){ int sum = 0; // Find the sum of array foreach (int it in A) { sum += it; } if (sum % 2 == 0) { // Initialise [,]dp with -1 for(int i = 0; i < 2001; i++) { for (int j = 0; j < 2001; j++) { dp[i, j] = -1; } } int ans = solve(A, 0, sum / 2, N); // No solution exists if (ans < 0 || ans > N) { Console.Write("-1" +"\n"); } // Otherwise else { Console.Write(ans +"\n"); } } // If sum is odd, no // subset is possible else { Console.Write("-1" +"\n"); }}// Driver Codepublic static void Main(String[] args){ int []A = { 2, 3, 1, 4 }; int N = A.Length; // Function Call minOp(A, N);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program for the above approach// Initialize dp[][]let dp= [];for(var i=0; i<2001; i++) { dp[i] = []; for(var j=0; j<2001; j++) { dp[i][j] = -1; }}// Function to find the minimum number// of operations to make sum of A[] 0function solve( A, i, sum, N){ // Initialize answer let res = 2001; // Base case if (sum < 0 || (i == N && sum != 0)) { return 2001; } // Otherwise, return 0 if (sum == 0 || i >= N) { dp[i][sum] = 0; return dp[i][sum]; } // Pre-computed subproblem if (dp[i][sum] != -1) { return dp[i][sum]; } // Recurrence relation for finding // the minimum of the sum of subsets res = Math.min(solve(A, i + 1, sum - A[i], N) + 1, solve(A, i + 1, sum, N)); // Return the result dp[i][sum] = res; return dp[i][sum];}// Function to find the minimum number// of elements required to be flipped// to make sum the array equal to 0function minOp(A, N){ let sum = 0; // Find the sum of array for (let i =0; i< A.length; i++) { sum += A[i]; } if (sum % 2 == 0) { let dp= []; for(var i=0; i<2001; i++) { dp[i] = []; for(var j=0; j<2001; j++) { dp[i][j] = -1; } } let ans = solve(A, 0, Math.floor(sum / 2), N); // No solution exists if (ans < 0 || ans > N) { document.write("-1 <br>"); } // Otherwise else { document.write(ans,"<br>"); } } // If sum is odd, no // subset is possible else { document.write("-1 <br>"); }}// Driver Codelet A = [ 2, 3, 1, 4 ];let N = A.length;// Function CallminOp(A, N);</script> |
Output
2
Time Complexity: O(S*N), where S is the sum of the given array.
Auxiliary Space: O(S*N)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Implementation :
C++
#include <bits/stdc++.h>using namespace std;// create DP to store previous computationsint dp[2001][2001];// Function to find the minimum number// of operations to make sum of A[] 0void minOp(vector<int>& A, int N){ int sum = 0; // Find the sum of array for (auto it : A) { sum += it; } if (sum % 2 == 0) { int target = sum / 2; // Initialize dp table for (int i = 0; i <= N; i++) { dp[i][0] = 0; } for (int j = 1; j <= target; j++) { dp[N][j] = 2001; } // Fill dp table in bottom-up manner for (int i = N - 1; i >= 0; i--) { for (int j = 1; j <= target; j++) { if (j >= A[i]) { dp[i][j] = min(dp[i + 1][j], dp[i + 1][j - A[i]] + 1); } else { dp[i][j] = dp[i + 1][j]; } } } // No solution exists if (dp[0][target] >= 2001) { cout << "-1" << endl; } // Otherwise else { cout << dp[0][target] << endl; } } // If sum is odd, no subset is possible else { cout << "-1" << endl; }}int main(){ vector<int> A = { 2, 3, 1, 4 }; int N = A.size(); // Function Call minOp(A, N); return 0;} |
Java
import java.util.Arrays;import java.util.List;public class Main { // create DP to store previous computations static int[][] dp; // Function to find the minimum number of operations to // make sum of A[] 0 static void minOp(List<Integer> A, int N) { int sum = 0; // Find the sum of the array for (int it : A) { sum += it; } if (sum % 2 == 0) { int target = sum / 2; // Initialize dp table dp = new int[N + 1][target + 1]; for (int i = 0; i <= N; i++) { Arrays.fill(dp[i], 0); } for (int j = 1; j <= target; j++) { dp[N][j] = 2001; } // Fill dp table in bottom-up manner for (int i = N - 1; i >= 0; i--) { for (int j = 1; j <= target; j++) { if (j >= A.get(i)) { dp[i][j] = Math.min( dp[i + 1][j], dp[i + 1][j - A.get(i)] + 1); } else { dp[i][j] = dp[i + 1][j]; } } } // No solution exists if (dp[0][target] >= 2001) { System.out.println("-1"); } // Otherwise else { System.out.println(dp[0][target]); } } else { // If the sum is odd, no subset is possible System.out.println("-1"); } } public static void main(String[] args) { List<Integer> A = Arrays.asList(2, 3, 1, 4); int N = A.size(); // Function Call minOp(A, N); }} |
Python
def min_op(A): sum = 0 # Find the sum of array for num in A: sum += num if sum % 2 == 0: target = sum // 2 N = len(A) # Initialize dp table dp = [[0 for _ in range(target + 1)] for _ in range(N + 1)] # Fill dp table in bottom-up manner for i in range(N - 1, -1, -1): for j in range(target, -1, -1): if j >= A[i]: dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - A[i]] + 1) else: dp[i][j] = dp[i + 1][j] # No solution exists if dp[0][target] == 0: print("-1") # Otherwise else: print(dp[0][target]) # If sum is odd, no subset is possible else: print("-1")if __name__ == "__main__": A = [2, 3, 1, 4] min_op(A) |
C#
using System;class GFG { // Function to find the minimum number // of operations to make sum of A[] 0 static void MinOp(int[] A, int N) { int sum = 0; // Find the sum of array foreach(var num in A) { sum += num; } if (sum % 2 == 0) { int target = sum / 2; // Initialize dp table int[, ] dp = new int[N + 1, target + 1]; for (int i = 0; i <= N; i++) { dp[i, 0] = 0; } for (int j = 1; j <= target; j++) { dp[N, j] = 2001; } // Fill dp table in bottom-up manner for (int i = N - 1; i >= 0; i--) { for (int j = 1; j <= target; j++) { if (j >= A[i]) { dp[i, j] = Math.Min( dp[i + 1, j], dp[i + 1, j - A[i]] + 1); } else { dp[i, j] = dp[i + 1, j]; } } } // No solution exists if (dp[0, target] >= 2001) { Console.WriteLine("-1"); } // Otherwise else { Console.WriteLine(dp[0, target]); } } // If sum is odd, no subset is possible else { Console.WriteLine("-1"); } } static void Main() { int[] A = { 2, 3, 1, 4 }; int N = A.Length; // Function Call MinOp(A, N); }} |
Javascript
// Function to find the minimum number// of operations to make sum of A[] 0function minOp(A) { const N = A.length; let sum = 0; // Find the sum of array for (let i = 0; i < N; i++) { sum += A[i]; } if (sum % 2 === 0) { const target = sum / 2; // Initialize dp table const dp = new Array(N + 1).fill(null).map(() => new Array(target + 1).fill(0)); for (let j = 1; j <= target; j++) { dp[N][j] = 2001; } // Fill dp table in bottom-up manner for (let i = N - 1; i >= 0; i--) { for (let j = 1; j <= target; j++) { if (j >= A[i]) { dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j - A[i]] + 1); } else { dp[i][j] = dp[i + 1][j]; } } } // No solution exists if (dp[0][target] >= 2001) { console.log("-1"); } // Otherwise else { console.log(dp[0][target]); } } else { // If sum is odd, no subset is possible console.log("-1"); }} const A = [2, 3, 1, 4]; minOp(A); |
Output
2
Time Complexity: O(S*N), where S is the sum of the given array.
Auxiliary Space: O(S*N)
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;// Function to find the minimum number// of operations to make sum of A[] 0int minOp(vector<int>& A, int N){ int sum = 0; // Find the sum of array for (auto it : A) { sum += it; } if (sum % 2 == 0) { int target = sum / 2; // Initialize dp table vector<int> dp(target + 1, 2001); dp[0] = 0; // Fill dp table in bottom-up manner for (int i = 0; i < N; i++) { for (int j = target; j >= A[i]; j--) { dp[j] = min(dp[j], dp[j - A[i]] + 1); } } // No solution exists if (dp[target] >= 2001) { cout << "-1" << endl; } // Otherwise else { cout << dp[target] << endl; } } // If sum is odd, no subset is possible else { cout << "-1" << endl; }}int main(){ vector<int> A = { 2, 3, 1, 4 }; int N = A.size(); // Function Call minOp(A, N); return 0;} |
Java
import java.util.Arrays;public class Main { // Function to find the minimum number of operations to // make the sum of A[] 0 static int minOp(int[] A, int N) { int sum = 0; // Find the sum of the array for (int value : A) { sum += value; } if (sum % 2 == 0) { int target = sum / 2; // Initialize dp table int[] dp = new int[target + 1]; Arrays.fill(dp, 2001); dp[0] = 0; // Fill dp table in a bottom-up manner for (int i = 0; i < N; i++) { for (int j = target; j >= A[i]; j--) { dp[j] = Math.min(dp[j], dp[j - A[i]] + 1); } } // No solution exists if (dp[target] >= 2001) { System.out.println("-1"); } // Otherwise else { System.out.println(dp[target]); } } // If the sum is odd, no subset is possible else { System.out.println("-1"); } return 0; } public static void main(String[] args) { int[] A = { 2, 3, 1, 4 }; int N = A.length; // Function Call minOp(A, N); }} |
Python
def min_op(A): N = len(A) sum_of_elements = sum(A) # Check if the sum of the elements is even if sum_of_elements % 2 == 0: target = sum_of_elements // 2 # Initialize a list to store the minimum operations required for each sum dp = [float('inf')] * (target + 1) dp[0] = 0 # Fill the dp list in a bottom-up manner for i in range(N): for j in range(target, A[i] - 1, -1): dp[j] = min(dp[j], dp[j - A[i]] + 1) # No solution exists if dp[target] == float('inf'): print("-1") else: print(dp[target]) else: # If the sum is odd, no subset is possible print("-1")if __name__ == "__main__": A = [2, 3, 1, 4] # Function Call min_op(A) |
C#
using System;class Program { // Function to find the minimum number of operations to // make the sum of A[] 0 static void MinOp(int[] A, int N) { int sum = 0; // Find the sum of the array foreach(int num in A) { sum += num; } if (sum % 2 == 0) { int target = sum / 2; // Initialize dp table int[] dp = new int[target + 1]; for (int i = 0; i <= target; i++) { dp[i] = 2001; } dp[0] = 0; // Fill dp table in bottom-up manner for (int i = 0; i < N; i++) { for (int j = target; j >= A[i]; j--) { dp[j] = Math.Min(dp[j], dp[j - A[i]] + 1); } } // No solution exists if (dp[target] >= 2001) { Console.WriteLine("-1"); } else { // Otherwise, print the minimum number of // operations Console.WriteLine(dp[target]); } } else { // If sum is odd, no subset is possible Console.WriteLine("-1"); } } static void Main() { int[] A = { 2, 3, 1, 4 }; int N = A.Length; // Function Call MinOp(A, N); }} |
Javascript
// Function to find the minimum number of operations to// make the sum of A[] 0function minOp(A, N) { let sum = 0; // Find the sum of the array for (let i = 0; i < N; i++) { sum += A[i]; } if (sum % 2 === 0) { let target = sum / 2; // Initialize dp table let dp = new Array(target + 1); for (let i = 0; i <= target; i++) { dp[i] = 2001; } dp[0] = 0; // Fill dp table in a bottom-up manner for (let i = 0; i < N; i++) { for (let j = target; j >= A[i]; j--) { dp[j] = Math.min(dp[j], dp[j - A[i]] + 1); } } // No solution exists if (dp[target] >= 2001) { console.log("-1"); } else { // Otherwise, print the minimum number of operations console.log(dp[target]); } } else { // If the sum is odd, no subset is possible console.log("-1"); }}// Test caseconst A = [2, 3, 1, 4];const N = A.length;// Function CallminOp(A, N); |
Output
2
Time Complexity: O(S*N), where S is the sum of the given array.
Auxiliary Space: O(target), where target is S/2
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
