# AbsDistinct

First one in the caterpillar section. We can solve it by creating two runners, one counting from start, the other one counting from the end of the array. As the array is sorted ascending, we can check which abs value is bigger, and decrease that one by one. If the value is the same on both runners, we simply move both of them while incrementing the distinct sum only once.

Another thing to note is that we must store the last value, because we cannot know if the last added number is the same.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
function solution(A) { var i=0, e = A.length - 1, last, tmp_last, sum = 0; while( i <= e ){ if( Math.abs( A[i] ) > Math.abs( A[e] ) ){ tmp_last = Math.abs( A[i] ); i++; } else if( Math.abs( A[i] ) === Math.abs( A[e] ) ){ tmp_last = Math.abs( A[i] ); e--; i++; }else{ tmp_last = Math.abs( A[e] ); e--; } if( tmp_last !== last || last === undefined ){ last = tmp_last; sum ++; } //console.log( A[i], A[e], sum ); } return sum; } |

Task description

A non-empty zero-indexed 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 zero-indexed 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.

Assume that:

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.

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.