Codility MinAbsSum

Question

I tried this Codility test: MinAbsSum. https://codility.com/programmers/lessons/17-dynamic_programming/min_abs_sum/

I solved the problem by searching the whole tree of possibilities. The results were OK, however, my solution failed due to timeout for large input. In other words the time complexity was not as good as expected. My solution is O(nlogn), something normal with trees. But this coding test was in the section "Dynamic Programming", and there must be some way to improve it. I tried with summing the whole set first and then using this information, but always there is something missing in my solution. Does anybody have an idea on how to improve my solution using DP?

#include <vector>
using namespace std;

int sum(vector<int>& A, size_t i, int s)
{
   if (i == A.size())     
      return s;

   int tmpl = s + A[i];
   int tmpr = s - A[i];
   return min (abs(sum(A, i+1, tmpl)), abs(sum(A, i+1, tmpr)));
}

int solution(vector<int> &A) {
   return sum(A, 0, 0);   
}

Answer 1

I invented another solution, better than the previous one. I do not use recursion any more. This solution works OK (all logical tests passed), and also passed some of the performance tests, but not all. How else can I improve it?

#include <vector>
#include <set> 
using namespace std;

int solution(vector<int> &A) {
    if (A.size() == 0) return 0;

    set<int> sums, tmpSums;        
    sums.insert(abs(A[0]));
    for (auto it = begin(A) + 1; it != end(A); ++it)
    {        
        for (auto s : sums)
        {
            tmpSums.insert(abs(s + abs(*it)));
            tmpSums.insert(abs(s - abs(*it)));            
        }
        sums = tmpSums;
        tmpSums.clear();
    }

    return *sums.begin();
}

Answer 2

I could not solve it. But here's the official answer.

Quoting it:

Notice that the range of numbers is quite small (maximum 100). Hence, there must be a lot of duplicated numbers. Let count[i] denote the number of occurrences of the value i. We can process all occurrences of the same value at once. First we calculate values count[i] Then we create array dp such that:

• dp[j] = −1 if we cannot get the sum j,
• dp[j] >= ­ 0 if we can get sum j.

Initially, dp[j] = -1 for all of j (except dp[0] = 0). Then we scan through all the values a appearing in A; we consider all a such that count[a]>0. For every such a we update dp that dp[j] denotes how many values a remain (maximally) after achieving sum j. Note that if the previous value at dp[j] >= 0 then we can set dp[j] = count[a] as no value a is needed to obtain the sum j. Otherwise we must obtain sum j-a first and then use a number a to get sum j. In such a situation dp[j] = dp[j-a]-1. Using this algorithm, we can mark all the sum values and choose the best one (closest to half of S, the sum of abs of A).

def MinAbsSum(A):
    N = len(A)
    M = 0
    for i in range(N):
        A[i] = abs(A[i])
        M = max(A[i], M)
    S = sum(A)
    count = [0] * (M + 1)
    for i in range(N):
        count[A[i]] += 1
    dp = [-1] * (S + 1)
    dp[0] = 0
    for a in range(1, M + 1):
        if count[a] > 0:
            for j in range(S):
                if dp[j] >= 0:
                    dp[j] = count[a]
                elif (j >= a and dp[j - a] > 0):
                    dp[j] = dp[j - a] - 1
    result = S
    for i in range(S // 2 + 1):
        if dp[i] >= 0:
            result = min(result, S - 2 * i)
    return result

(note that since the final iteration only considers sums up until S // 2 + 1, we can save some space and time by only creating a DP Cache up until that value as well)

The Java answer provided by fladam returns wrong result for input [2, 3, 2, 2, 3], although it gets 100% score.

Java Solution

import java.util.Arrays;

public class MinAbsSum{
    static int[] dp;

    public static void main(String args[]) {
        int[] array = {1, 5,  2, -2};

        System.out.println(findMinAbsSum(array));
    }
    
    public static int findMinAbsSum(int[] A) {
        int arrayLength = A.length;
        int M = 0;
        for (int i = 0; i < arrayLength; i++) {
            A[i] = Math.abs(A[i]);
            M = Math.max(A[i], M);
        }
        
        int S = sum(A);
        dp = new int[S + 1];
        int[] count = new int[M + 1];
        for (int i = 0; i < arrayLength; i++) {
            count[A[i]] += 1;
        }
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 1; i < M + 1; i++) {
            if (count[i] > 0) {
                for(int j = 0; j < S; j++) {
                    if (dp[j] >= 0) {
                        dp[j] = count[i];
                    } else if (j >= i && dp[j - i] > 0) {
                        dp[j] = dp[j - i] - 1;
                    }
                }
            }
        }
        int result = S;
        for (int i = 0; i < Math.floor(S / 2) + 1; i++) {
            if (dp[i] >= 0) {
                result = Math.min(result, S - 2 * i);
            }
        }
        return result;
    }

    public static int sum(int[] array) {
        int sum = 0;
        for(int i : array) {
            sum += i;
        }

        return sum;
    }
}

Answer 3

This solution (in Java) scored 100% for both (correctness and performance)

public int solution(int[] a){
    if (a.length == 0) return 0;
    if (a.length == 1) return a[0];
    int sum = 0;
    for (int i=0;i<a.length;i++){
        sum += Math.abs(a[i]);
    }
    int[] indices = new int[a.length];
    indices[0] = 0;
    int half = sum/2;
    int localSum = Math.abs(a[0]);
    int minLocalSum = Integer.MAX_VALUE;
    int placeIndex = 1;
    for (int i=1;i<a.length;i++){
        if (localSum<half){
            if (Math.abs(2*minLocalSum-sum) > Math.abs(2*localSum - sum))
                minLocalSum = localSum;
            localSum += Math.abs(a[i]);
            indices[placeIndex++] = i;
        }else{
            if (localSum == half)
                return Math.abs(2*half - sum);

            if (Math.abs(2*minLocalSum-sum) > Math.abs(2*localSum - sum))
                minLocalSum = localSum;
            if (placeIndex > 1) {
                localSum -= Math.abs(a[indices[placeIndex--]]);
                i = indices[placeIndex];
            }
        }
    }
    return (Math.abs(2*minLocalSum - sum));

}

this solution treats all elements like they are positive numbers and it's looking to reach as close as it can to the sum of all elements divided by 2 (in that case we know that the sum of all other elements will be the same delta far from the half too -> abs sum will be minimum possible ). it does so by starting with the first element and successively adding others to the "local" sum (and recording indices of elements in the sum) until it reaches sum of x >= sumAll/2. if that x is equal to sumAll/2 we have an optimal solution. if not, we go step back in the indices array and continue picking other element where last iteration in that position ended. the result will be a "local" sum having abs((sumAll - sum) - sum) closest to 0;

fixed solution:

public static int solution(int[] a){
    if (a.length == 0) return 0;
    if (a.length == 1) return a[0];
    int sum = 0;
    for (int i=0;i<a.length;i++) {
        a[i] = Math.abs(a[i]);
        sum += a[i];
    }
    Arrays.sort(a);

    int[] arr = a;
    int[] arrRev = new int[arr.length];
    int minRes = Integer.MAX_VALUE;

    for (int t=0;t<=4;t++) {
        arr = fold(arr);
        int res1 = findSum(arr, sum);
        if (res1 < minRes) minRes = res1;

        rev(arr, arrRev);
        int res2 = findSum(arrRev, sum);
        if (res2 < minRes) minRes = res2;

        arrRev = fold(arrRev);
        int res3 = findSum(arrRev, sum);
        if (res3 < minRes) minRes = res3;
    }

    return minRes;
}

private static void rev(int[] arr, int[] arrRev){
    for (int i = 0; i < arrRev.length; i++) {
        arrRev[i] = arr[arr.length - 1 - i];
    }
}

private static int[] fold(int[] a){
    int[] arr = new int[a.length];
    for (int i=0;a.length/2+i/2 < a.length && a.length/2-i/2-1 >= 0;i+=2){
        arr[i] = a[a.length/2+i/2];
        arr[i+1] = a[a.length/2-i/2-1];
    }
    if (a.length % 2 > 0) arr[a.length-1] = a[a.length-1];
    else{
        arr[a.length-2] = a[0];
        arr[a.length-1] = a[a.length-1];
    }
    return arr;
}

private static int findSum(int[] arr, int sum){
    int[] indices = new int[arr.length];
    indices[0] = 0;
    double half = Double.valueOf(sum)/2;
    int localSum = Math.abs(arr[0]);
    int minLocalSum = Integer.MAX_VALUE;
    int placeIndex = 1;
    for (int i=1;i<arr.length;i++){
        if (localSum == half)
            return 2*localSum - sum;
        if (Math.abs(2*minLocalSum-sum) > Math.abs(2*localSum - sum))
            minLocalSum = localSum;

        if (localSum<half){
            localSum += Math.abs(arr[i]);
            indices[placeIndex++] = i;
        }else{
            if (placeIndex > 1) {
                localSum -= Math.abs(arr[indices[--placeIndex]]);
                i = indices[placeIndex];
            }
        }
    }

    return Math.abs(2*minLocalSum - sum);
}