Given an array of positive elements, you have to flip the sign of some of its elements such that the resultant sum of the elements of array should be minimum non-negative (as close to zero as possible). Return the minimum no. of elements whose sign needs to be flipped such that the resultant sum is minimum non-negative. Note that the sum of all the array elements will not exceed 104.
Examples:
Input: arr[] = {15, 10, 6}
Output: 1
Here, we will flip the sign of 15
and the resultant sum will be 1.
Input: arr[] = [14, 10, 4]
Output: 1
Here, we will flip the sign of 14 and the resultant sum will be 0.
Note that flipping the signs of 10 and 4 also gives
the resultant sum 0 but the count of flipped elements is not minimum.
Naive approach: For each element A[i], 0 ? i < n of the array, we have 2 options.
- Sign of A[i] is flipped(-ve).
- Sign of A[i] is not flipped(+ve).
So we can have total 2n possible configurations of the array. We can maintain the sum of elements and number of flips in each configuration and keep a track of minimum sum (Ties are broken by the minimum number of flips).The number of flips in the minimum sum configuration will be the answer.
Time Complexity: O(2n) where n is number of elements in the array.
Efficient approach: This problem can be solved using dynamic programming and is a variation of standard 0/1 knapsack problem. The difference is that we have 2 options there i.e. either to include an item in the knapsack or exclude it and here it is like to flip the sign of element or not. Instead of bag weight in knapsack problem, here it is the sum of all elements of the array without flipping (which is maximum 104 given in problem statement).
Optimal Substructure: Let dp[i][j] be the minimum number of flips required in the first i elements of the array to make the sum equal to j.
1 ? i ? n and -sum ? j ? sum where sum is sum of all elements of array without flipping.
If sign of ar[i – 1] is not flipped to make sum = j
dp[i][j] = dp[i – 1][j – A[i – 1]]
If sign of ar[i – 1] is flipped to make sum = j
dp[i][j] = min(dp[i][j], dp[i – 1][j + A[i – 1]]+1)
Note: Since the sum of elements of the array could be negative after flipping. So we can not use a 2D array for tabulation because in dp[i][j], j is the sum and indexes of the array cannot be negative. Thus, we are going to use an array of Hash maps. Size of the array will be n + 1.
Overlapping Subproblems: Just like 0/1 knapsack problem, there are overlapping subproblems here. We don’t need to evaluate results again and again but instead, we can store results of subproblems in a table.
Time complexity: O(n * sum)
Auxiliary Space: O(n * sum)
where n is number of elements and sum is sum of elements of the array without flipping.
Space optimization: If you take a closer look at the optimal substructure, dp[i][j] will depends only on dp[i – 1][j – A[i – 1]]/dp[i – 1][j + A[i – 1]]. So, there is involvement of only 2 rows i and i – 1. Thus, we need only 2 rows instead of n + 1.
Following are the changes that we need to optimize space.
- Instead of taking array size=n+1 declare array of size=2.
- Introduce a boolean variable (say flag) to toggle between maps.We can initialize dp[0] map and start filling dp[1].In the next iteration, dp[0] is the current map and dp[1] is previous.In this way, we can keep on toggling between the 2 maps.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the // minimum number of elements// whose sign must be flipped // to get the positive// sum of array elements as close // to 0 as possibleint solve(int A[], int n){ // Array of unordered_map of size=2. unordered_map<int, int> dp[2]; // boolean variable used for // toggling between maps bool flag = 1; // Calculate the sum of all // elements of the array int sum = 0; for (int i = 0; i < n; i++) sum += A[i]; // Initializing first map(dp[0]) // with INT_MAX because // for i=0, there are no elements // in the array to flip for (int i = -sum; i <= sum; i++) dp[0][i] = INT_MAX; // Base Case dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = -sum; j <= sum; j++) { dp[flag][j] = INT_MAX; if (j - A[i - 1] <= sum && j - A[i - 1] >= -sum) dp[flag][j] = dp[flag ^ 1][j - A[i - 1]]; if (j + A[i - 1] <= sum && j + A[i - 1] >= -sum && dp[flag ^ 1][j + A[i - 1]] != INT_MAX) dp[flag][j] = min(dp[flag][j], dp[flag ^ 1][j + A[i - 1]] + 1); } // For toggling flag = flag ^ 1; } // Required sum is minimum non-negative // So, we iterate from i=0 to sum and find // the first i where dp[flag ^ 1][i] != INT_MAX for (int i = 0; i <= sum; i++) { if (dp[flag ^ 1][i] != INT_MAX) return dp[flag ^ 1][i]; } // In worst case we will flip max n-1 elements return n - 1;}// Driver codeint main(){ int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); cout << solve(arr, n); return 0;} |
Java
// Java implementation of // the above approach:class GFG { // Function to return the // minimum number of elements // whose sign must be flipped // to get the positive // sum of array elements as close // to 0 as possible public static int solve(int[] A, int n) { int[][] dp = new int[2000][2000]; // boolean variable used for // toggling between maps int flag = 1; // Calculate the sum of all // elements of the array int sum = 0; for (int i = 0; i < n; i++) sum += A[i]; // Initializing first map(dp[0]) // with INT_MAX because for i=0, // there are no elements in the // array to flip for (int i = -sum; i <= sum; i++) { try { dp[0][i] = Integer.MAX_VALUE; } catch (Exception e) { } } // Base Case dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= sum; j++) { try { dp[flag][j] = Integer.MAX_VALUE; if (j - A[i - 1] <= sum && j - A[i - 1] >= -sum) dp[flag][j] = dp[flag ^ 1][j - A[i - 1]]; if (j + A[i - 1] <= sum && j + A[i - 1] >= -sum && dp[flag ^ 1][j + A[i - 1]] != Integer.MAX_VALUE) dp[flag][j] = Math.min( dp[flag][j], dp[flag ^ 1][j + A[i - 1]] + 1); } catch (Exception e) { } } // For toggling flag = flag ^ 1; } // Required sum is minimum non-negative // So, we iterate from i=0 to sum and find // the first i where dp[flag ^ 1][i] != INT_MAX for (int i = 0; i <= sum; i++) { if (dp[flag ^ 1][i] != Integer.MAX_VALUE) return dp[flag ^ 1][i]; } // In worst case we will flip max n-1 elements return n - 1; } // Driver code public static void main(String[] args) { int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.length; System.out.println(solve(arr, n)); }}// This code is contributed by sanjeev2552 |
Python3
# Python3 implementation of the approach# Function to return the minimum # number of elements# whose sign must be flipped # to get the positive# sum of array elements as close # to 0 as possibledef solve(A, n): dp = [[0 for i in range(2000)] for i in range(2000)] # boolean variable used for # toggling between maps flag = 1 # Calculate the sum of all # elements of the array sum = 0 for i in range(n): sum += A[i] # Initializing first map(dp[0]) # with INT_MAX because # for i=0, there are no elements # in the array to flip for i in range(-sum, sum+1): dp[0][i] = 10**9 # Base Case dp[0][0] = 0 for i in range(1, n+1): for j in range(-sum, sum+1): dp[flag][j] = 10**9 if (j - A[i - 1] <= sum and j - A[i - 1] >= -sum): dp[flag][j] = dp[flag ^ 1][j - A[i - 1]] if (j + A[i - 1] <= sum and j + A[i - 1] >= -sum and dp[flag ^ 1][j + A[i - 1]] != 10**9): dp[flag][j] = min(dp[flag][j], dp[flag ^ 1][j + A[i - 1]] + 1) # For toggling flag = flag ^ 1 # Required sum is minimum non-negative # So, we iterate from i=0 to sum and find # the first i where dp[flag ^ 1][i] != INT_MAX for i in range(sum+1): if (dp[flag ^ 1][i] != 10**9): return dp[flag ^ 1][i] # In worst case we will flip max n-1 elements return n - 1# Driver codearr = [10, 22, 9, 33, 21, 50, 41, 60]n = len(arr)print(solve(arr, n))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the above approach: using System;class GFG {// Function to return the minimum number // of elements whose sign must be flipped // to get the positive sum of array elements // as close to 0 as possiblepublic static int solve(int[] A, int n) { int[,] dp = new int[2000, 2000]; // boolean variable used for // toggling between maps int flag = 1; // Calculate the sum of all elements // of the array int sum = 0; for (int i = 0; i < n; i++) sum += A[i]; // Initializing first map(dp[0]) with // INT_MAX because for i=0, there are // no elements in the array to flip for (int i = -sum; i <= sum; i++) { try { dp[0, i] = int.MaxValue; } catch (Exception e){} } // Base Case dp[0, 0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= sum; j++) { try { dp[flag, j] = int.MaxValue; if (j - A[i - 1] <= sum && j - A[i - 1] >= -sum) dp[flag, j] = dp[flag ^ 1, j - A[i - 1]]; if (j + A[i - 1] <= sum && j + A[i - 1] >= -sum && dp[flag ^ 1, j + A[i - 1]] != int.MaxValue) dp[flag, j] = Math.Min(dp[flag, j], dp[flag ^ 1, j + A[i - 1]] + 1); } catch (Exception e) {} } // For toggling flag = flag ^ 1; } // Required sum is minimum non-negative // So, we iterate from i=0 to sum and find // the first i where dp[flag ^ 1,i] != INT_MAX for (int i = 0; i <= sum; i++) { if (dp[flag ^ 1, i] != int.MaxValue) return dp[flag ^ 1, i]; } // In worst case we will flip // max n-1 elements return n - 1;}// Driver codepublic static void Main(String[] args){ int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.Length; Console.WriteLine(solve(arr, n));}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JS implementation of the approach// Function to return the // minimum number of elements// whose sign must be flipped // to get the positive// sum of array elements as close // to 0 as possiblefunction solve(A, n){ // Array of unordered_map of size=2. let dp = [], H = 2000, // 4 rows W = 2000; // of 6 cellsfor ( var y = 0; y < H; y++ ) { dp[ y ] = []; for ( var x = 0; x < W; x++ ) { dp[ y ][ x ] = 0; }} // boolean variable used for // toggling between maps let flag = 1; // Calculate the sum of all // elements of the array let sum = 0; for (let i = 0; i < n; i++) sum += A[i]; // Initializing first map(dp[0]) // with INT_MAX because // for i=0, there are no elements // in the array to flip for (let i = -sum; i <= sum; i++) dp[0][i] = Number.MAX_VALUE; // Base Case dp[0][0] = 0; for (let i = 1; i <= n; i++) { for (let j = -sum; j <= sum; j++) { dp[flag][j] = Number.MAX_VALUE; if (j - A[i - 1] <= sum && j - A[i - 1] >= -sum) dp[flag][j] = dp[flag ^ 1][j - A[i - 1]]; if (j + A[i - 1] <= sum && j + A[i - 1] >= -sum && dp[flag ^ 1][j + A[i - 1]] != Number.MAX_VALUE) dp[flag][j] = Math.min(dp[flag][j], dp[flag ^ 1][j + A[i - 1]] + 1); } // For toggling flag = flag ^ 1; } // Required sum is minimum non-negative // So, we iterate from i=0 to sum and find // the first i where dp[flag ^ 1][i] != MAX_VALUE for (let i = 0; i <= sum; i++) { if (dp[flag ^ 1][i] != Number.MAX_VALUE) return dp[flag ^ 1][i]; } // In worst case we will flip max n-1 elements return n - 1;}// Driver codelet arr = [ 10, 22, 9, 33, 21, 50, 41, 60 ];let n = arr.length;document.write(solve(arr, n));// This code is contributed by rohitsingh07052.</script> |
3
Time complexity: O(n * sum).
Auxiliary Space: O(sum) where n is number of elements and sum is sum of elements of the array without flipping.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
