Minimize difference with 0 after adding or subtracting any element of the given Array
Given an array arr[] of N integers, the task is to find the minimum difference from 0 after adding or subtracting any element of the array from it.
Examples:
Input: N = 4, arr[] = {1, 2, 1, 3}
Output: 1
Explanation: Add 1 and 2 with 0 and subtract 1 and 3.
So total sum = (1 + 2 – 1 – 3) = -1. Difference is 1.Input: N = 3, arr[] = {3, 3, 3}
Output: 3
Explanation: No matter which order is chosen, the minimum possible difference is 3.Input: N = 1, arr[] = {100}
Output: 100
Explanation: There is only one element so difference will be 100
Brute Force Approach: We are using a bitmask to represent each combination. The outer loop iterates over all possible bitmasks from 0 to 2^N – 1 (inclusive), where N is the number of elements in the array. The inner loop iterates over each element in the array and includes or excludes it from the sum based on whether the corresponding bit in the current bitmask is 1 or 0. The minimum difference found so far is updated in each iteration.
- Initialize minDiff to the maximum long long value.
- For each possible subset of the input array (excluding the empty subset and the full subset):
- Initialize sum to 0.
- For each element of the input array:
- If the jth element is included in the current subset:
- Add the jth element to sum.
- If the jth element is not included in the current subset:
- Subtract the jth element from sum.
- If the jth element is included in the current subset:
- Update minDiff to the minimum value between minDiff and the absolute value of sum.
- Return minDiff as the result.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h> using namespace std; // Function to find the minimum difference long long minDist( int * arr, int N) { long long minDiff = LLONG_MAX; // Initialize minimum difference to maximum long long value for ( int i = 0; i < (1 << N); i++) { long long sum = 0; for ( int j = 0; j < N; j++) { if (i & (1 << j)) // Include the jth element in the sum sum += arr[j]; else // Exclude the jth element from the sum sum -= arr[j]; } minDiff = min(minDiff, abs (sum)); } return minDiff; } // Driver code int main() { int arr[] = { 1, 2, 1, 3 }; int N = sizeof (arr) / sizeof (arr[0]); cout << minDist(arr, N); return 0; } |
Java
import java.lang.Math; public class Main { public static int minDist( int [] arr, int N) { int minDiff = Integer.MAX_VALUE; // Initialize minimum difference to maximum integer value for ( int i = 0 ; i < ( 1 << N); i++) { int sum = 0 ; for ( int j = 0 ; j < N; j++) { if ((i & ( 1 << j)) > 0 ) { // Include the jth element in the sum sum += arr[j]; } else { // Exclude the jth element from the sum sum -= arr[j]; } } minDiff = Math.min(minDiff, Math.abs(sum)); } return minDiff; } // Driver code public static void main(String[] args) { int [] arr = { 1 , 2 , 1 , 3 }; int N = arr.length; System.out.println(minDist(arr, N)); } } // This code is contributed by shivhack999 |
Python3
import sys # Function to find the minimum difference def minDist(arr, N): minDiff = sys.maxsize # Initialize minimum difference to maximum integer value for i in range ( 1 << N): sum = 0 for j in range (N): if i & ( 1 << j): # Include the jth element in the sum sum + = arr[j] else : # Exclude the jth element from the sum sum - = arr[j] minDiff = min (minDiff, abs ( sum )) return minDiff # Driver code arr = [ 1 , 2 , 1 , 3 ] N = len (arr) print (minDist(arr, N)) |
C#
//C# code for the above approach using System; public class GFG{ static long MinDist( int [] arr) { long minDiff = long .MaxValue; // Initialize minimum difference to maximum long value int N = arr.Length; for ( int i = 0; i < (1 << N); i++) { long sum = 0; for ( int j = 0; j < N; j++) { if ((i & (1 << j)) != 0) // Include the jth element in the sum sum += arr[j]; else // Exclude the jth element from the sum sum -= arr[j]; } minDiff = Math.Min(minDiff, Math.Abs(sum)); } return minDiff; } public static void Main() { int [] arr = { 1, 2, 1, 3 }; Console.WriteLine(MinDist(arr)); } } // This code is contributed by suchethan |
Javascript
// Function to find the minimum difference function minDist(arr) { let minDiff = Number.MAX_SAFE_INTEGER; // Initialize minimum difference to maximum safe integer value for (let i = 0; i < (1 << arr.length); i++) { let sum = 0; for (let j = 0; j < arr.length; j++) { if (i & (1 << j)) // Include the jth element in the sum sum += arr[j]; else // Exclude the jth element from the sum sum -= arr[j]; } minDiff = Math.min(minDiff, Math.abs(sum)); } return minDiff; } // Driver code const arr = [1, 2, 1, 3]; const result = minDist(arr); console.log(result); |
1
Time Complexity: O(N * 2N)
Auxiliary Space: O(1)
Approach: The problem focusses on forming an Exponential Recursive Tree where there are two possibilities each time. One to add element and one to subtract it. Follow the given steps:
- Create a recursive function minDist having arguments original array arr, iterating index r starting from 0, length of the array N, and integer to calculate current distance k.
- If r becomes equal to n means all elements are traversed so return current distance k.
- Else return minimum of minDist(arr, r+1, N, k+arr[r]) and minDist(arr, r+1, N, k-arr[r]).
Below is the implementation of the above approach.
C++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum difference long long minDist( int * arr, int r, int N, long long k) { if (r == N) return k; else return min( abs (minDist(arr, r + 1, N, k + arr[r])), abs (minDist(arr, r + 1, N, k - arr[r]))); } // Driver code int main() { int arr[] = { 1, 2, 1, 3 }; int N = sizeof (arr) / sizeof (arr[0]); cout << minDist(arr, 0, N, 0); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to find the minimum difference static long minDist( int arr[ ], int r, int N, long k) { if (r == N) return k; else return Math.min(Math.abs(minDist(arr, r + 1 , N, k + arr[r])), Math.abs(minDist(arr, r + 1 , N, k - arr[r]))); } public static void main (String[] args) { int arr[] = { 1 , 2 , 1 , 3 }; int N = arr.length; System.out.print(minDist(arr, 0 , N, 0 )); } } // This code is contributed by hrithikgarg03188 |
Python3
# Python code to implement above approach # Function to find the minimum difference def minDist(arr, r, N, k): if (r = = N): return k else : return min ( abs (minDist(arr, r + 1 , N, k + arr[r])), abs (minDist(arr, r + 1 , N, k - arr[r]))) # Driver code arr = [ 1 , 2 , 1 , 3 ] N = len (arr) print (minDist(arr, 0 , N, 0 )) # This code is contributed by gfgking |
C#
// C# program for the above approach using System; class GFG { // Function to find the minimum difference static long minDist( int [] arr, int r, int N, long k) { if (r == N) return k; else return Math.Min(Math.Abs(minDist(arr, r + 1, N, k + arr[r])), Math.Abs(minDist(arr, r + 1, N, k - arr[r]))); } public static void Main() { int [] arr = { 1, 2, 1, 3 }; int N = arr.Length; Console.Write(minDist(arr, 0, N, 0)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code to implement above approach // Function to find the minimum difference const minDist = (arr, r, N, k) => { if (r == N) return k; else return Math.min(Math.abs(minDist(arr, r + 1, N, k + arr[r])), Math.abs(minDist(arr, r + 1, N, k - arr[r]))); } // Driver code let arr = [1, 2, 1, 3]; let N = arr.length; document.write(minDist(arr, 0, N, 0)); // This code is contributed by rakeshsahni </script> |
1
Time Complexity: O(2N)
Auxiliary Space: O(1)
Approach: By using Dynamic Programming
This approach involves sorting the given array in non-decreasing order. Then, we can traverse the array and add the first half of the array elements and subtract the second half of the array elements from 0. The minimum difference is then returned as the answer. The time complexity of this approach is O(NlogN) due to sorting.
Algorithm steps of code approach –
- Calculate the range of possible sums by summing all the elements of the given array.
- Initialize a dynamic programming table `dp` of size `(N+1) x (range+1)` where `N` is the number of elements in the array and `range` is the range of possible sums calculated in step 1. Initialize `dp[0][0]` to `true`.
- For each `i` from 1 to `N` and each `j` from 0 to `range`, set `dp[i][j]` to `dp[i-1][j]` if `arr[i-1] > j`, otherwise choose the minimum of `dp[i-1][j-arr[i-1]]` (including the current element) and `dp[i-1][j]` (excluding the current element) and set `dp[i][j]` to that minimum value.
- Traverse the second half of the possible sums, i.e., from `0` to `range/2`. For each sum `j`, check if `dp[N][j]` is `true`, where `N` is the number of elements in the array. If `dp[N][j]` is `true`, update the `minDiff` variable as the minimum of the current `minDiff` and `range – 2*j`.
- Return `minDiff` as the answer.
- End of the Program.
Below is the implementation of the above approach.
C++
// c++ code implementation by using above approche #include <bits/stdc++.h> using namespace std; // Function to find the minimum difference long long minDist( int * arr, int N) { long long range = accumulate(arr, arr + N, 0); // Calculate the range of possible sums vector<vector< bool >> dp(N+1, vector< bool >(range+1, false )); // Initialize dp table dp[0][0] = true ; for ( int i = 1; i <= N; i++) { for ( int j = 0; j <= range; j++) { if (arr[i-1] > j) { // Current element cannot be included dp[i][j] = dp[i-1][j]; } else { // Choose the minimum of including or excluding the current element dp[i][j] = dp[i-1][j] || dp[i-1][j-arr[i-1]]; } } } long long minDiff = LLONG_MAX; for ( int j = 0; j <= range/2; j++) { if (dp[N][j]) { minDiff = min(minDiff, range - 2*j); } } return minDiff; } // Driver code k int main() { int arr[] = { 1, 2, 1, 3 }; int N = sizeof (arr) / sizeof (arr[0]); // function calling cout << minDist(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.Arrays; public class Main { // Function to find the minimum difference static long minDist( int [] arr, int N) { long range = Arrays.stream(arr) .sum(); // Calculate the range of // possible sums boolean [][] dp = new boolean [N + 1 ][( int )(range + 1 )]; // Initialize dp table dp[ 0 ][ 0 ] = true ; for ( int i = 1 ; i <= N; i++) { for ( int j = 0 ; j <= range; j++) { if (arr[i - 1 ] > j) { // Current element // cannot be included dp[i][j] = dp[i - 1 ][j]; } else { // Choose the minimum of including or // excluding the current element dp[i][j] = dp[i - 1 ][j] || dp[i - 1 ][j - arr[i - 1 ]]; } } } long minDiff = Long.MAX_VALUE; for ( int j = 0 ; j <= range / 2 ; j++) { if (dp[N][j]) { minDiff = Math.min(minDiff, range - 2 * j); } } return minDiff; } // Driver code public static void main(String[] args) { int [] arr = { 1 , 2 , 1 , 3 }; int N = arr.length; // Function calling System.out.println(minDist(arr, N)); } } |
Python3
# Function to find the minimum difference between two subsets def minDist(arr): N = len (arr) range_sum = sum (arr) # Calculate the range of possible sums dp = [[ False for _ in range (range_sum + 1 )] for _ in range (N + 1 )] # Initialize dp table dp[ 0 ][ 0 ] = True # Dynamic programming loop to fill the dp table for i in range ( 1 , N + 1 ): for j in range (range_sum + 1 ): if arr[i - 1 ] > j: # If the current element is too large to be included dp[i][j] = dp[i - 1 ][j] else : # Choose the minimum of including or excluding the current element dp[i][j] = dp[i - 1 ][j] or dp[i - 1 ][j - arr[i - 1 ]] minDiff = float ( 'inf' ) # Find the minimum difference by iterating through the second half of the dp table for j in range (range_sum / / 2 + 1 ): if dp[N][j]: minDiff = min (minDiff, range_sum - 2 * j) return minDiff # Driver code arr = [ 1 , 2 , 1 , 3 ] result = minDist(arr) print (result) |
C#
using System; class MinimumDifference { // Function to find the minimum difference static long MinDist( int [] arr, int N) { long range = 0; foreach ( int num in arr) { range += num; // Calculate the range of possible sums } bool [,] dp = new bool [N + 1, range + 1]; // Initialize dp table dp[0, 0] = true ; for ( int i = 1; i <= N; i++) { for ( int j = 0; j <= range; j++) { if (arr[i - 1] > j) // Current element cannot be included { dp[i, j] = dp[i - 1, j]; } else // Choose the minimum of including or excluding the current element { dp[i, j] = dp[i - 1, j] || dp[i - 1, j - arr[i - 1]]; } } } long minDiff = long .MaxValue; for ( int j = 0; j <= range / 2; j++) { if (dp[N, j]) { minDiff = Math.Min(minDiff, range - 2 * j); } } return minDiff; } static void Main( string [] args) { int [] arr = { 1, 2, 1, 3 }; int N = arr.Length; // Function calling Console.WriteLine(MinDist(arr, N)); } } |
Javascript
// Function to find the minimum difference function minDist(arr, N) { const range = arr.reduce((sum, num) => sum + num, 0); // Calculate the range of possible sums const dp = new Array(N + 1).fill( null ).map(() => new Array(range + 1).fill( false )); // Initialize dp table dp[0][0] = true ; for (let i = 1; i <= N; i++) { for (let j = 0; j <= range; j++) { if (arr[i - 1] > j) { // Current element cannot be included dp[i][j] = dp[i - 1][j]; } else { // Choose the minimum of including or excluding the current element dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]]; } } } let minDiff = Number.MAX_SAFE_INTEGER; for (let j = 0; j <= Math.floor(range / 2); j++) { if (dp[N][j]) { minDiff = Math.min(minDiff, range - 2 * j); } } return minDiff; } // Driver code const arr = [1, 2, 1, 3]; const N = arr.length; // Function calling console.log(minDist(arr, N)); |
1
Time Complexity: O(2^N * N) since there are 2^N possible subsets of the input array.
Auxiliary space: O(1).
Contact Us