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

Task

A non-empty vector A consisting of N integers is given. Vector 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 vector 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 vector 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 vector 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 vector 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 vector is 1000. Assuming that the first element of the vector is 0 and the rest of the elements of the vector are 1000 each, then the absolute maximum difference is (N-1) x 1000, where N is the number of vector 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 vector.

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 vector; and the second nested for-loop, does the right-hand sum of the vector. The subtraction and comparison takes place in the outer for-loop, below. The brute force code is (read the code and comments):

fn solution(a: &Vec<i32>) -> i32 {
    let n = a.len();
    
    let mut ads_min_diff: i32 = 1000 * (n as i32); 
    
    for p in 1..n {
        let mut left_sum = 0;  //sum of left part
        let mut right_sum = 0;  //sum of right part
        for i in 0..p {
            left_sum = left_sum + a[i];
        }
        for j in p..n {
            right_sum = right_sum + a[j]; 
        }

        let mut diff = right_sum - left_sum;
        if diff < 0 {
            diff = -diff;  //to obtain absolute difference
        }
        if diff < ads_min_diff {
            ads_min_diff = diff;
        }
    }
    
    return ads_min_diff;
}

fn main() {
    let b = vec![3, 1, 2, 4, 3];
    let minl = solution(&b);
    println!("{}", minl);
}

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 vector, 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 vector (vector) is obtained in one initial scan of the vector. That is one linear time of O(n).

Having gotten the totalSum, only one scan through all the elements in the vector 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):

fn solution(a: &Vec<i32>) -> i32 {
    let n = a.len();
    
    let mut total_sum = 0;
    
    for i in 0..n {
        total_sum += a[i];
    }
    
    let mut ads_min_diff: i32 = 1000 * (n as i32); 
    let mut left_sum = 0;
    for i in 1..n {
        left_sum = left_sum + a[i-1];
        let right_sum = total_sum - left_sum;
        let mut diff = left_sum - right_sum;
        if diff < 0 {
            diff = -diff;  //to obtain absolute difference, equivalent to x -1.
        }
        if diff < ads_min_diff {
            ads_min_diff = diff;
        }
    }
    
    return ads_min_diff;
}

fn main() {
    let b = vec![3, 1, 2, 4, 3];
    let minl = solution(&b);
    println!("{}", minl);
}

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 vector is obtained in a running sum fashion. The sum of the left part of the vector 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.