# Solution to Abs-Distinct by codility

29 Jan

Question Name: AbsDistinct

In the original requirement, expected worst-case space complexity is O(N). But actually, O(1) is enought.

### 25 Replies to “Solution to Abs-Distinct by codility”

• Sheng says:

FYI: if hash table is permitted, one line in Python is enough:
return len(set([abs(item) for item in A]))
I love Pythonnnnn!!!

• Vitor says:

I know this is rather ancient thread, but do you mind if I post a Java 8 stream one-line solution, just for fun?

• Vitor says:
1. Piotrek Martynowicz says:

Scarface, Codility’s complexity detection is just trying to guess (I don’t know how, though) but Sheng’s solution is O(N).

• Sheng says:

I do not know the details neither. But the detection complexity is not very accurate, as I talked with the staffs in Codility.

• Sheng says:

Thanks for sharing!

• Sheng says:

Thanks for sharing!

• Mikhail Manukhin says:

Pavel,
Your solution fails for input: [-2147483648, -2147483648]
Array A is sorted in non-decreasing order, i.e. not necessarily in increasing.

• Sheng says:

Thanks for figuring out!

• Sheng says:

You do not need to convert set to list to use len() function.

• Jeffrey Coho says:

Correct me if I’m wrong but I think he converted to a set to only capture distinct elements

• Sheng says:

Yes. But before the convert and in the for loop, (s)he transfers all input to their absolute values.

2. micropentium6 says:

3. Tony Sun says:

Hi, can someone please elaborate a bit more on the key idea behind Caterpillar method? I read the document from codility and can sort of understand that it normally requires using two indices. But I feel I don’t fully understand the key principle of this idea.
On LeetCode, there is one tag called Two Pointer; is the idea of two pointer the same as caterpillar method?
Thanks.

4. Rajasekar says:

C# solution,

5. CB says:

C++

6. Woz says:

Thanks for the website, have learnt a lot!

Here is a O(n) time O(1) space Python solution. It’s slightly simpler and easier to reason than the code in your original post, but it’s basically the same thing.

7. George Raafat says:

This is a simpler solution with 100 percent score::

8. Sebastian says:

C# Code

or

9. Luiz doleron says:

This is my C++ version: https://app.codility.com/demo/results/trainingJ3QVPG-PGD/

The single difference for the Sheng’s Python version is that in C++ we must to deal with the overflow of INT_MIN.