Lesson 13: AbsDistinct (abs distinct)

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

This is an easy problem. 

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.

#include <math.h>

int solution(int A[], int N) 
{    
    int l = 0;
    int r = N - 1;
    
    int cnt = 0;
    
    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;
}

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.

This gives the 100% score.

I guess those that are using the languages with BigInteger or so won't suffer from such a bug...

#include <math.h>

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;
}

NOTE: some people does something like 'len(set([abs(x) for x in A]))' in Python. This may not give the O(N) time complexity. 

Since the insertion to the Set must be performed for N times, the cost can be multiplied by the insertion cost. 

Some may claim the use of a hash table would result in O(1) for the insertion, however, as the worst-case space complexity is O(N) and N[1..100,000] and the range of the array A is [−2,147,483,648..2,147,483,647], it is expected that different values may share the same hash (unless we prepare a table with the length of ULONG_MAX(the max value of unsigned 32bit integer), which causes a collision in the hash table.

In this case we can't not expect the insertion to be always O(1), and the worst case time complexity when such collisions occur for the insertion is O(N).