Problem

Let A be a non-empty array consisting of N integers. 

The abs sum of two for a pair of indices (P, Q) is the absolute value |A[P] + A[Q]|, for 0 <= P <= Q < N.

For example, the following array A: 

  A[0] =  1

  A[1] =  4

  A[2] = -3

has pairs of indices (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2). 

The abs sum of two for the pair (0, 0) is A[0] + A[0] = |1 + 1| = 2.

The abs sum of two for the pair (0, 1) is A[0] + A[1] = |1 + 4| = 5.

The abs sum of two for the pair (0, 2) is A[0] + A[2] = |1 + (−3)| = 2.

The abs sum of two for the pair (1, 1) is A[1] + A[1] = |4 + 4| = 8.

The abs sum of two for the pair (1, 2) is A[1] + A[2] = |4 + (−3)| = 1.

The abs sum of two for the pair (2, 2) is A[2] + A[2] = |(−3) + (−3)| = 6.

Write a function: 

    function solution(A);

that, given a non-empty array A consisting of N integers, returns the minimal abs sum of two for any pair of indices in this array. 

For example, given the following array A:

  A[0] =  1

  A[1] =  4

  A[2] = -3 

the function should return 1, as explained above.

Given array A: 

  A[0] = -8

  A[1] =  4

  A[2] =  5

  A[3] =-10

  A[4] =  3

the function should return |(−8) + 5| = 3. 

Write an efficient algorithm for the following assumptions:

·         N is an integer within the range [1..100,000];

·         each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

Note:

The same element can be summed and the absolute value obtained or any two elements from any two positions in either order, can be summed and the absolute value obtained. 

The JavaScript predefined function to obtain the absolute value is abs() in the math library. So, the math.h header has to be included.

Need for Sorting

There are two given data list examples, which are 

    const V1 = [1, 4, -3];

and 

    const V2 = [-8, 4, 5, -10, 3];

If the first list is sorted ascending, it would be: 

    -3, 1, 4

A caterpillar can crawl through this sorted list and detect |4 + (−3)| = 1, the minimum absolute sum of a pair (of two). 

If this list included 0, then sorted, the list would have been:

    -3, 0, 1, 4 

and the minimal abs sum of two, would have been |0 + 0| = 0. The sorted list without 0 is:  -3, 1, 4

If the second list is sorted, it would be: 

    -10 -8, 3, 4, 5

A caterpillar can crawl through this sorted list and detect |(−8) + 5| = 3, the minimum absolute sum of a pair. 

If this list included 0, then sorted, the list would have been:

    -10 -8, 0, 3, 4, 5 

and the minimal abs sum of two would have been |0 + 0| = 0. The sorted list without 0 is: -10 -8, 3, 4, 5

One Element Only

One of the assumptions in the problem description is:

·         N is an integer within the range [1..100,000]; 

This means that a given list can contain just one element. In this case abs(A[0]+A[0]) is returned as the minimum absolute sum of two (a pair).

Strategy

If the given list has only one element, then return abs(A[0]+A[0]). 

Next sort the given list in ascending order.

The variable for the index of the caterpillar’s front legs is front. The variable for the index of the caterpillar’s back legs is back. 

Let front be 0.

While (front < N) AND  (A[front] < 0), increment front repeatedly. If front remains at zero for the whole scan, then all the elements are positive. If front becomes N, then all the elements are negative (excluding 0). If the sorted list begins with the smallest negative number and ends with the biggest positive number, then front will become the index for the value just before the first positive value (which may be zero if zero is an element).                

If all the values are positive, without 0 as in,

    +1, +2, +3, +4 

, then the minimum absolute sum of two is 2 x A[0] = 2 x (+1) = +1+1 = abs(+1+1) = 2. 

If all the values are negative without 0 as in, 

    -3, -2, -1

then the minimum absolute sum of two is abs(A[N-1] + A[N-1]) = abs(-1+-1) = abs(-1-1) = abs(-2) = 2. Note that A[N-1] + A[N-1] is same as 2 * A[N-1]. 

The rest of the following steps handle cases where there are negative and positive numbers with or without 0, sorted ascending, as in

which happens to be without 0. Note that A[0] is -3, and not -1 or not +1, or not 0 if 0 was there as a value. 

At the start, the index, front is 2 for -1. The index, back is chosen as:

            int back = front - 1;   

This means that back is 2 - 1 = 1 (index).

From this point, where front and back are consecutive indexes, the front legs will either be incremented by 1 or the back legs be decremented by 1, in possibly repeating and alternating fashion, until the minimum absolute sum of two is obtained. Note that if the list has a 0 value, then |0+0| is returned. 

Actually, in a while-loop, the front legs are incremented, if A[back]+A[front] is less than 0 and the back legs are decremented, otherwise. In this way, the assumed minimum result is moving towards zero. This is a special caterpillar.

Smart Program

The program is (read the code and comments): 

<script type='text/javascript'>
    "use strict";

    function solution(A) {
        let N = A.length;
        if (N==1) return Math.abs(A[0]+A[0]);

        A.sort((a, b) => a - b);    //sort ascending
    
        let front=0;
        while (front<N && A[front]<0)
            front++;                     

        if (front==0)    //all positive integer values, if front still remains at index 0
                return 2*A[0];   
        if (front==N)    //all negative integer values, if front became N
                return Math.abs(A[N-1] + A[N-1]);  
         
        let back=front-1;   
        let current;
    
        let min=Math.abs(A[0]+A[0]);   
        while ( back>=0 && front<N ) {
            current=Math.abs(A[back]+A[front]);
            if (current<min)
                min=current;
            if (min==0)
                break;  
                
            if (A[back]+A[front]<0)
                front++;  
            else 
                back--;
        }
        return min;    
    }

    let V1 = [1, 4, -3];
    let ret1 = solution(V1);
    document.write(ret1 + '<br>');

    const V2 = [-8, 4, 5, -10, 3];
    let ret2 = solution(V2);
    document.write(ret2 + '<br>');

</script>

The output is 

    1

    3

At app.codility.com/programmers the scoring and detected time complexity for this solution() function is: 

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O(N * log(N))

Remarks

Two techniques have been used to solve the problem. The techniques are: sorting and the caterpillar method. Sorting was taught in lesson 6.