The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Task

A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])| .

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example, consider array A such that:

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

We can split this tape in four places:

        P = 1, difference = |3 − 10| = 7
        P = 2, difference = |4 − 9| = 5
        P = 3, difference = |6 − 7| = 1
        P = 4, difference = |10 − 3| = 7

Write a function:

    int solution(int A[], int N);

that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.

For example, given:

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

the function should return 1, as explained above.

Write an efficient algorithm for the following assumptions:

    - N is an integer within the range [2..100,000];
    - each element of array A is an integer within the range [−1,000..1,000].

The algorithm should run in O(N) time.

Notes:

P is an index variable of the array from 1 to N-2 (neither part must be empty).

In the problem, it is indicated towards the bottom, that the maximum possible value in the array is 1000. Assuming that the first element of the array is 0 and the rest of the elements of the array are 1000 each, then the absolute maximum difference is (N-1) x 1000, where N is the number of array elements given. If this is made N x 1000, the resulting program will still be alright.

So, in the solution, the initial absolute minimum difference would be considered as N x 1000. When the actual first absolute minimum difference is obtained, it is compared to N x 1000. It will likely be smaller and that will be the new minimum. The next absolute difference obtained will be compared to this new minimum; and if it is smaller, that will become the next new minimum. This will continue till the end of the array.

This task can be solved in a brute force way or in a smarter way. The brute-force way is treated first.

Brute-Force Solution

In the brute force solution, there are three for-loops: one outer for-loop and two nested for-loops at the same level (in parallel). For each iteration of the outer for-loop, the first nested for-loop does the sum for the left-hand part of the array; and the second nested for-loop, does the right-hand sum of the array. The subtraction and comparison takes place in the outer for-loop, below. The brute force code is (read the code and comments):

    #include <stdio.h> 

    int solution(int A[], int N) {
        int adsMinDiff = 1000 * N;

        for (int p = 1; p < N; p++) {
            int leftSum = 0;  //sum of left part
            int rightSum = 0;  //sum of right part
            for (int i=0; i<p; i++)
                leftSum = leftSum + A[i];
            for (int j=p; j<N; j++)
                rightSum = rightSum + A[j]; 

            int diff = rightSum - leftSum;
            if (diff < 0)
                diff = -diff;  //to obtain absolute difference
            if (diff < adsMinDiff)
                adsMinDiff = diff;
        }
        return adsMinDiff;
    }

The score is:

    Task score : 69% -  Correctness : 100% ; Performance : 33%
    Detected time complexity: O(N * N) = O(n2)

This means that the correct answer for the absolute minimum difference is always obtained for any given array, with this approach, but the speed is slow, especially for long arrays.

Smarter Solution

With the smarter solution, the totalSum for all the elements in the array (array) is obtained in one initial scan of the array. That is one linear time of O(n).

Having gotten the totalSum, only one scan through all the elements in the array is necessary again. For each element A[i] , as the scanning continues, the current leftSum is obtained by just adding the new left element to the previous leftSum; and the rightSum is obtained by just subtracting the leftSum from the totalSum. The current difference is then determined. The immediate result (current difference) may be positive or negative. If it is negative, it has to be made positive, by just multiplying with -1. Remember, it is the absolute difference that is required. This should be the new temporary minimum, which has to be compared with the next minimum. The code is (read through the code and comments):

    #include <stdio.h> 

    int solution(int A[], int N) {
        int totalSum = 0;

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

        int adsMinDiff = 1000 * N;
        int leftSum = 0;
        for (int i = 1; i < N; i++) {
            leftSum = leftSum + A[i-1];
            int rightSum = totalSum - leftSum;
            int diff = leftSum - rightSum;
            if (diff < 0)
                diff = -diff;  //to obtain absolute difference, equivalent to x -1.
            if (diff < adsMinDiff)
                adsMinDiff = diff;
        }

        return adsMinDiff;
    }

    int main() 
    { 
        int B[] = {3, 1, 2, 4, 3};
        int N = sizeof(B) / sizeof(B[0]);    //divide size of array by size of one (first) element

        int minl = solution(B, N);

        printf("%i\n", minl);

        return 0; 
    } 

The output is:

    1

The score is:

    Task score : 100% -  Correctness : 100% ; Performance : 100%
    Detected time complexity : O(N)

The speed is now high. The detected time complexity is O(N). The time complexity is actually O(2N), for the two for-loops. However, the coefficient (multiplier) is usually omitted when quoting the complexity.

Conclusion

To solve the problem or a similar one, get the total-sum first, in one scan. In another scan, get the left and right totals for their elements; and before the next iteration, get the difference, its absolute value, and do a comparison. The final answer is the least of the values compared.

The total sum of the whole array is obtained in a running sum fashion. The sum of the left part of the array is also obtained in a running sum fashion. The sum of the right part is obtained by subtracting the running sum of the left part, from the total sum.