Codility - Min Abs Sum Of Two

https://codility.com/programmers/lessons/13

Let A be a non-empty zero-indexed 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:

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

that, given a non-empty zero-indexed 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.

http://codility-lessons.blogspot.com/2015/03/lesson-13-minabssumoftwo.html
First, we sort the array in ascending order.

If the maximum value is negative or zero or if the minimum value is positive or zero, we already have the answer. 

If not, then use two cursors to check the values in the array, one of which move from left to right and other moves from right to left. We name them 'l' and 'r' respectively.

If the value at the position 'l' is still negative and its absolute value is bigger than the other end we move 'l' to the next position. If the absolute value at the position 'r' is bigger, then move the 'r' to the next position. If the absolute values of these two are equal, then move both.

If the value at the position l is larger than or equal to zero, we can terminate the search just there.
https://github.com/acprimer/Codility/blob/master/src/Lesson13/MinAbsSumOfTwo.java
    public int solution(int[] A) {
        Arrays.sort(A);
        int ans = Math.abs(A[0]) * 2;
        int p = 0, q = A.length - 1;
        while (p < q) {
            ans = Math.min(ans, Math.abs(A[p] + A[p]));
            ans = Math.min(ans, Math.abs(A[q] + A[q]));
            ans = Math.min(ans, Math.abs(A[p] + A[q]));
            if (ans == 0) return 0;
            else if (A[p] + A[q] > 0) {
                q--;
            } else p++;
            if ((A[p] > 0 && A[q] > 0) || (A[p] < 0 && A[q] < 0)) {
                break;
            }
        }
        return ans;
    }
https://codesolutiony.wordpress.com/2015/01/11/13-4-minabssumoftwo/

    public int solution(int[] A) {

        Arrays.sort(A);

        int start = 0;

        int end = A.length - 1;

        int result = Math.abs(A[0] * 2);

        while (start < end) {

            int cur = Math.min(Math.abs(A[start] + A[end]), Math.min(Math.abs(A[start] * 2), Math.abs(A[end]*2)));

            if (cur == 0) {

                return 0;

            }

            result = Math.min(result, cur);

            if (A[start] >= 0 || A[end] <= 0) {

                break;

            }

            if (start + 1 < end) {

                if (Math.abs(A[start + 1] + A[end]) < Math.abs(A[start] + A[end - 1])) {

                    start ++;

                } else {

                    end --;

                }

            } else {

                break;

            }

        }

        return result;

    }

int solution(int A[], int N) { //first we sort in the ascending order qsort(A, N, sizeof(int), compare_int); int l = 0; int r = N - 1; //the initial value for the min int min = abs(A[0] + A[0]); while(l <= r){ int lval = abs(A[l] * 2); int rval = abs(A[r] * 2); int both = abs(A[l] + A[r]); //update the min value if (lval < min){ min = lval; } if (rval < min){ min = rval; } if (both < min){ min = both; } //we A[l] >=0, we have the smallest number already. if (A[l] >= 0){ break; } //move the positions. if (lval < rval){ r--; } else if (lval > rval){ l++; } else { r--; l++; } } return min; }
Python Solution: http://www.martinkysel.com/codility-minabssumoftwo-solution/