An algorithm to find the min value of the difference between the sum of all numbers from all possible two parts to which it can be divided

The solution is the min absolute value of |(A[0] + … + A[D-1]) – (A[D] + … + A[N-1])| where A is an on-empty zero-indexed array A consisting of N integers.

Assumptions

  • The range of the array size is [2..100,000];
  • The rage of the elements of this array is [−1,000..1,000].

Example:

A[0] = 2 | A[1] = 3 | A[2] = 4

This array can be splited in two parts.

D = 1 – diff = |2 − 7| = 7
D = 2 – diff = |5 − 4| = 1

The result for it will be 1.

Solution

public int algo(int[] A) {
    int size = A.length;
    int result = Integer.MAX_VALUE;
    int sumLeft = 0;
    int sumRight = 0;
    for ( int i=0; i < size; i++ ) {
        sumRight += A[i];
    }
    for ( int i=0; i < (size-1); i++ ) {
        sumLeft  +=A[i];
        sumRight -=A[i];
        int diff = Math.abs(sumLeft - sumRight);
        if ( diff < result ) {
            result = diff;
        }
    }
    return result;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s