You have given an array of Integer. You can change the sign of any element of the array. Write a program-me to find minimum sum of the given array.
For Example: 2 1 3 4 2
Minimum sum = 0 if -2, -1, -3 , 4, 2
Approach: Problem can be reduced to dividing a sequence of integers into two sets such that the sum of the digits in one set is equal to the sum of the digits in the other set.
public class MinimumSum {
public static boolean calculate(int arr[], int tot, int totalSum)
{
int n = arr.length;
boolean dp[][] = new boolean[totalSum+1][n+1];
if(dp[tot][n-1] == false)
{
for(int i = 0; i < n; i++)
dp[arr[i]][i] = true;
int sum = arr[0];
for(int k = 1; k < n; k++)
{
sum += arr[k];
int lim = tot < sum ? tot : sum;
for(int i = 1; i <=lim; i++)
{
dp[i][k] |= dp[i][k-1];
if(i > arr[k])
dp[i][k] |= dp[i-arr[k]][k-1];
}
}
}
return dp[tot][n-1];
}
public static int solve(int arr[])
{
int n = arr.length;
int tot = 0;
if (n == 1)
return arr[0];
for(int i = 0; i < n; i++)
{
tot += arr[i];
}
int min_sum = Integer.MAX_VALUE;
for(int i = 1; i <= tot/2; i++)
{
boolean temp1, temp2;
temp1 = calculate(arr, i,tot);
temp2 = calculate(arr, tot - i,tot);
if((temp1 == true) && (temp2 == true))
{
if(min_sum > (tot-i-i))
min_sum = tot - i - i;
}
}
return min_sum;
}
public static void main(String[] args) {
int arr[] = {2,1,3,4,2};
System.out.println("elements min sum"+solve(arr));
}
}
No comments:
Post a Comment