Lesson 13: MinAbsSumOfTwo (Min Abs Sum Of Two)

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

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.

#include <alloca.h> #include <memory.h> #include <math.h> int compare_int(const void *a, const void *b) { //don't do 'return *(int*)a - *(int*)b;', //as it can cause underflow or overflow. if (*(int*)a == *(int*)b){ return 0; } if (*(int*)a < *(int*)b){ return -1; } return 1; } 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; }