Codility - Abs-Distinct

https://codility.com/c/intro/demoS5JR9J-2K8

The array is sorted in non-decreasing order. The absolute distinct count of this array is the number of distinct absolute values among the elements of the array.

For example, consider array A such that:

  A[0] = -5
  A[1] = -3
  A[2] = -1
  A[3] =  0
  A[4] =  3
  A[5] =  6

The absolute distinct count of this array is 5, because there are 5 distinct absolute values among the elements of this array, namely 0, 1, 3, 5 and 6.

http://codility-lessons.blogspot.com/2015/03/lesson-13-absdistinct-abs-distinct.html
We prepare two cursors. One of them 'l' scan the array from left to right, and the other 'r' from the right to left. 

If abs(A[l]) > abs(A[r]), we move the left cursor one more step. 
If abs(A[l]) < abs(A[r]), we move the right cursor one more step. 
If abs(A[l]) == abs(A[r]), we move both. 

In any case of the above, we increment the counter, as we found an absolute distinct value.

It must be noted that each element of the Array A may have the same as its neighbor(s) (like [-5, -4, -4, -4, 0, 1, 1, 1...]). If so, we have to skip the value at the next position and move the cursor further.

The code gives the 90% correctness score, but the 100% performance, as it fails in the arith_overlow test.

Yes, I made a bug. Due to the range of the integer value in C (32bit in the Codilitiy's environment, −2,147,483,648..2,147,483,647),  abs(−2,147,483,648) becomes −2,147,483,648. 

So we check the left most element of A[] and if it is equal to −2,147,483,648, we keep on moving to the left first, until we found the value that can safely be applied the 'abs' function.

https://github.com/acprimer/Codility/blob/master/src/Lesson13/AbsDistinct.java

We can change it to just traverse once.

    public int solution(int[] A) {

        int newLength = 0;

        for(int i=1;i<A.length;i++) {

            if(A[i]!=A[newLength]) {

                A[++newLength] = A[i];

            }

        }

        int ans = ++newLength;

        int left = 0, right = 0;

        while (left < newLength && A[left] < 0) left++;

        right = left;

        left--;

        while (left >= 0 && right < newLength) {

            if (A[left] + A[right] == 0) {

                ans--;

                left--;

                right++;

            } else if (A[left] + A[right] > 0) {

                left--;

            } else right++;

        }

        return ans;

    }

int solution(int A[], int N) 
{    
    int l = 0;
    int r = N - 1;
    
    int cnt = 0;
    
    //we can't handle abs(-2147483648). Since the max value for int is
    //2147483647, abs(-2147483648) becomes -2147483648.  
    if (A[l] == -2147483648){
        cnt++;
        while(l < N && A[l] == -2147483648){
            l++;
        }
    }
    
    while(l <= r){
        
        int absl = abs(A[l]);
        int absr = abs(A[r]);
        
        //we are sure we are going to find one distinct number.
        cnt++;
        
        //move the cursor 
        if (absl < absr){
            //skip if the same abs value is found in the new position.
            while(r > 0 && absr == abs(A[r])){
                r--;
            }
        }
        else if (absl > absr){
            //skip if the same abs value is found in the new position.
            while(l < N && absl == abs(A[l])){
                l++;
            }
        }
        else {
            //skip if the same abs value is found in the new position.
            while(r > 0 && absr == abs(A[r])){
                r--;
            }
            while(l < N && absl == abs(A[l])){
                l++;
            }
        }
    
    }
    
    return cnt;
}

http://blog.csdn.net/caopengcs/article/details/41841325
给定一个按非递减顺序排好顺序的非空整数数组，问里面右多少种不同的绝对值。

数据范围：整数数组长度[1..10^5], 整数范围[-2147483648, +2147483647]。

要求复杂度 ： 时间O(N),空间O(1)

分析： 题目不难…… 但是细节很重要。因为整数直接取绝对值可能回溢出（例如-2147483648),而且我们没有额外空间hash。所以一个好办法是类似合并两个有序序列。我们从最小的负数和最大的正数开始类似归并排序那么做。这样，正负数都是按照绝对值逐渐减小的顺序遍历的。我们把正数和负数的绝对值想像成两个递减的序列，然后按归并排序思路，每次大的动一下就可以了，直到一个列表为空的时候，我们需要把另外一个列表计算进去。要点就是可以用x + y的符号来代替绝对值比较，因为一个正数 ＋ 负数 不会溢出。。。。

Using Hashset - O(n) space

http://www.martinkysel.com/codility-absdistinct-solution/

def solution(A):

    return len(set([abs(x) for x in A]))

http://codesays.com/2014/solution-to-abs-distinct-by-codility/