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;
}