Problem

A non-empty array A consisting of N numbers is given. 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.

Write a function: 

    function solution(A);

that, given a non-empty array A consisting of N numbers, returns absolute distinct count of array A. 

For example, given array A such that:

  A[0] = -5

  A[1] = -3

  A[2] = -1

  A[3] =  0

  A[4] =  3

  A[5] =  6 

the function should return 5, as explained above.

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 [−2,147,483,648..2,147,483,647];

·         array A is sorted in non-decreasing order. 

Note:

“non-decreasing order” means ascending order.

Absolute distinct count means that a negative number and its positive counterpart, must be counted once and not twice (or three or more times). The given array is: 

    const A = [-5, -3, -1, 0, 3, 6];

-3 and 3 which is +3 must be counted once (from left to right). And so the number of distinct absolute values is 5, for this given list. The -5 at index zero has nothing to do with this total count. The -5 is at index 0 and not at some negative index. The -5 itself at index zero, is counted once as 5. 

The topic for this problem is caterpillar method. So the candidate should expect that the caterpillar method is used somewhere, somehow.

By definition, absolute value means the magnitude. For example, the absolute value of -3 is 3 and the absolute value of +3 is still 3. The magnitude is always a positive quantity. 

Do not forget that the list is already sorted, and in ascending order.

Counting Issues

One kind of counting issues occurs when there are two numbers with the same magnitude but with opposite signs, as with -3 and 3 above. 

Another kind of counting issues occurs when the same number occurs more than once. In the following list, -4 occurs more than once:

    const A = [-5, -4, -4, -4, -3, -1, 0, 3, 6]; 

In the following list, +5 occurs more than once:

    const A = [-5, -4, -3, -1, 0, 3, 5, 5, 5, 5, 6]; 

Since the given array is already sorted, not by you the candidate, then repeating numbers will lie next to one another.

Analysis

One of the assumptions in the problem description is:

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

This means that the length (size) of the array given, can be one, with one negative or one positive integer. Since there are no two numbers that are the same or no two numbers with opposite signs but same magnitude, the number of distinct absolute values here, is just 1, and 1 is returned.

If all the numbers occur from 0 downwards, negatively, or all the numbers occur from 0 upwards, positively, then the only issue in this situation, would be repetition. The code segment for this situation is: 

    let count=1;
    if (A[0]>=0 || A[N-1]<=0){
        for (int i=1;i<N;i++) {
            if (A[i]!=A[i-1])    //not repetition 
                count++;
        }
        return count;
    

Remember that the list is already sorted, and in this case, count has to start from index 1, because the given array is non-empty. The caterpillar is not involved here. Repetition has been taken care of by the if-statement, “if (A[i]!=A[i-1]) count++;”.

A special (kind of) caterpillar is needed to solve the problem when there are negative numbers, as well as possible numbers, in the list. Remember that the list is already sorted.

Special Caterpillar

The caterpillar here is different from the caterpillar learned in the lesson. Here, the front legs of the caterpillar start at the end, index N-1, and the back legs start at the beginning, index 0. The caterpillar here crawls by shrinking, either by moving the front legs backwards, one index at a time, or by moving the back legs forward, one index at a time. The process ends when the front and back legs are at the same index. This same index ended at, is not necessarily in the middle of the given list. 

Note that the back legs start at index 0, and not at some negative integer (index).

Counting is done only when the magnitude of the element for the front legs is different from the magnitude of the element for the back legs (this avoids counting the same positive and negative numbers more than once, and avoids counting repetition of the same number). In other words, the counter, count is incremented by 1, only when the magnitude of the number for the front legs is different from the magnitude of the number for the back legs. 

The magnitude of a number is obtained using the abs() function in the math JavaScript library. So the math.h header has to be included into the program.

And so, when are the front legs moved backwards or when are the back legs moved forward? After the counter has just been incremented, if the magnitude of the number for the back legs is greater than the magnitude of the number for the front legs, then the back legs are moved one index forward. This movement continues as long as the new element ahead is the same as the previous back element (avoid repetition), and as long as the value zero, if present, will not be crossed (going forward). There is no counting (incrementing counter) for this phase. 

After the counter has just been incremented, if the magnitude of the number for the front legs is less than the magnitude of the number for the back legs, then the front legs are moved one index backwards. This movement continues as long as the new element behind is the same as the previous front element (avoid repetition), and as long as the value zero, if present, will not be crossed (going backwards). There is no counting (incrementing counter) for this phase.

Seen another way: After the counter has just been incremented, if the back and front elements are of opposite signs, but the same in magnitude, then the back index is incremented by 1, if the value zero, if present, will not be crossed (going forward). Or next, the front index is decremented by 1, if the value zero, if present, will not be crossed (going backwards). Or without incrementing the back index or decrementing the front index, when it would mean the front and back indexes are at the same point, and there, the function should return. There is no counting (incrementing counter) for this phase. 

Smart Solution

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 1;
    let count=1;

    if (A[0]>=0 || A[N-1]<=0){
        for (let i=1;i<N;i++) {
            if (A[i]!=A[i-1]) count++;
        }
        return count;
    }

    let back = 0;
    let front = N-1;
    
    let ab, af;

    while(back!=front){

        ab = Math.abs(A[back]);
        af = Math.abs(A[front]);

        if (ab!=af) count++;
        
        if (ab>af && A[back+1]<=0){
            
            back++;
            while(A[back]==A[back-1] && A[back+1]<=0) back++;    //at least two elements remaining after back++
            
        } else if (ab<af && A[front-1]>=0){         
            front--;
            while(A[front]==A[front+1] && A[front-1]>=0) front--;    //at least two elements remaining after front++
            
        }else{
            if (A[back+1]<=0) back++;
            else if (A[front-1]>=0) front--;
            else return count; 
        }
    }
    
    return count;
}

    const A = [-5, -3, -1, 0, 3, 6];

    let ret = solution(A);

    document.write(ret + '<br>');       

</script>

The output is: 5.

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

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

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