CODEWITHSUNDEEP
javaarraysalgorithmtime-complexity
Arefe
Arefe

Reputation: 12417

find the lowest absolute sum of elements from an array

I try to understand a solution from a problem in the Codility provided below,

For a given array A of N integers and a sequence S of N integers from the set {−1, 1}, we define val(A, S) as follows:

val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }|

(Assume that the sum of zero elements equals zero.)

For a given array A, we are looking for such a sequence S that minimizes val(A,S).

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A of N integers, computes the minimum value of val(A,S) from all possible values of val(A,S) for all possible sequences S of N integers from the set {−1, 1}.

For example, given array:

  A[0] =  1
  A[1] =  5
  A[2] =  2
  A[3] = -2

your function should return 0, since for S = [−1, 1, −1, 1], val(A, S) = 0, which is the minimum possible value.

Assume that:

N is an integer within the range [0..20,000];
each element of array A is an integer within the range [−100..100].
Complexity:

expected worst-case time complexity is O(N*max(abs(A))2); expected worst-case space complexity is O(N+sum(abs(A))) (not counting the storage required for input arguments).

I have the solution that I'm trying to understand for the last few hours. 

public static int solution(int[] A) {

        int N = A.length;

        int sum = 0;
        int max = 0;

        for (int i = 0; i < N; i++) {

            A[i] = Math.abs(A[i]);
            sum += A[i];

            max = Math.max(A[i], max);
        }


        int[] counts = new int[max + 1];

        for (int i = 0; i < N; i++) {
            counts[A[i]] += 1;
        }

        int[] Total = new int[sum + 1];

        Arrays.fill(Total, -1);
        Total[0] = 0;

        // Segment I
        for (int i = 1; i <= max; i++) {

            if (counts[i] > 0) {

                for (int j = 0; j <= sum; j++) {

                    // j th index is zero or positive
                    if (Total[j] >= 0) {
                        Total[j] = counts[i];
                    }
                    // (i-j) th index is positive
                    else if ((j - i) >= 0 && Total[j - i] > 0) {
                        Total[j] = Total[j - i] - 1;
                    }
                }
            }
        }

        int result = sum;

        // Segment II
        for (int i = 0; i < sum / 2 + 1; i++) {

            // i- th index if zero or positive
            // BODMAS_RULE = {Brackets, Orders, Division, Multiplication, Addition, Subtraction}
            if (Total[i] >= 0) {
                result = Math.min(result, sum - 2 * i);
            }
        }

        return result;
    }

If anyone can explain whats going on in the last 2 segments of the loops, it will be very helpful. All I look for a brief explanation within few lines of text.

UPADTE

I would like to understand why do we use conditions in the for loop of the first segment. Besides, why do we iterate till the sum / 2 + 1 in the second for loop. Thank you.

Upvotes: 4

Views: 2867

Answers (1)

MBo
MBo

Reputation: 80187

To make sum with required property, you can find subset of array A with sum as close as possible to half of overall sum.

It is kind of well-known subset sum problem and might be solved with dynamic programming approach using additional array with dimension corresponding to the overall sum (note array Total).

Note that solution from the question deals with positive numbers only, so you have to modify it for using negative numbers (like your example A[3] = -2).

This code makes array total of length sum+1 and holds counts for every value in array counts.

At the first stage code fills total table with non-nengative entries for all possible sums. Consider simple set value:count (2:3; 3:2).
First round fills entries 0,2,4,6 with values 3,2,1,0. Second round changes all non-negative entries by number of threes and
builds decreasing sequences for chains from non-negative entries (for example, 4--> 4+3 ->4+6). After that we have total array [2,-1,2,1,2,1,2,1,0,1,0,-1,0] with negative entries (impossible sums) at 1,11. Note that such approach does not store information - what items have been used to make every possible sum, so you have to make more modifications.

Upvotes: 4

Related Questions