Given an array of integers, find the lowest absolute sum of elements.
- Difficulty Level: Hard
- Question URL: https://app.codility.com/programmers/lessons/17-dynamic_programming/min_abs_sum/
- Time Complexity:
Solution:
Solution to Codility's Minimum Absolute Sum problem which is from the Codility Lesson 17: Dynamic programming and, is solved in Java 8 with 100% performance and correctness scores. The goal here is to given an array of integers, find the lowest absolute sum of elements. You can find the question of this MinAbsSum problem in the Codility website.
package Codility.Lesson17;
import java.util.*;
public class MinAbsSum {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a1 = { 1, 5, 2, -2 };
int result = solution(a1);
System.out.println(result);
}
public static int solution(int[] A) {
// main idea:
// using "dynamic programming" to build up the solution
// (bottom up)
if (A.length == 0)
return 0;
if (A.length == 1)
return A[0];
int sum = 0;
int max = A[0];
for (int i = 0; i < A.length; i++) {
A[i] = Math.abs(A[i]);
sum += A[i];
max = Math.max(A[i], max);
}
int[] count = new int[max + 1];
for (int num : A) {
count[num]++;
}
int[] dp = new int[sum + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int i = 0; i <= max; i++) {
if (count[i] > 0) {
for (int val = 0; val <= sum; val++) {
if (dp[val] >= 0)
dp[val] = count[i];
else if (val >= i && dp[val - i] > 0) {
dp[val] = dp[val - i] - 1;
}
}
}
}
int result = sum;
for (int i = 0; i <= sum / 2; i++) {
if (dp[i] >= 0)
result = Math.min(result, sum - (2 * i));
}
return result;
}
}