Solution to Abs-Distinct by codility

29 Jan

January 29, 2014 Sheng 25

Question: https://codility.com/demo/take-sample-test/abs_distinct

Question Name: AbsDistinct

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

def solution(A):

abs_distinct = 1

current = max(abs(A[0]), abs(A[-1]))

index_head = 0

index_tail = len(A)-1

while index_head <= index_tail:

# We travel the array from the greatest

# absolute value to the smallest.

former = abs(A[index_head])

if former == current:

# Skip the heading elements, whose

# absolute values are the same with

# current recording one.

index_head += 1

continue

latter = abs(A[index_tail])

if latter == current:

# Skip the tailing elements, whose

# absolute values are the same with

# current recording one.

index_tail -= 1

continue

# At this point, both the former and

# latter has different absolute value

# from current recorded one.

if former >= latter:

# The next greatest value is former

current = former

index_head += 1

else:

# The next greatest value is latter

current = latter

index_tail -= 1

# Meet with a new absolute value

abs_distinct += 1

return abs_distinct

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

Strange, but this solution gives me 100% with O(N*log(N)) detected complexity (C# variant: https://codility.com/demo/results/demoBBF8PJ-MRN/). The Caterpillar approach is a bit faster than my previous super-compact solution with the use of a HashSet: https://codility.com/demo/results/demoNYE9BD-9ZK/ (O(N*log(N)) complexity too)

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

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

import java.util.Arrays;

public class AbsDistinct {

public int solution(int[] A) {

// write your code in Java SE 8

return (int)Arrays.stream(A).map(a->a<0?-a:a).distinct().count();

}

Vitor says:
February 11, 2018 at 6:53 pm

https://app.codility.com/demo/results/training3D5AAX-8VY/
Reply

Piotrek Martynowicz says:
October 7, 2014 at 10:53 am
Scarface, Codility’s complexity detection is just trying to guess (I don’t know how, though) but Sheng’s solution is O(N).
Reply
- Sheng says:
  October 7, 2014 at 2:30 pm
  I do not know the details neither. But the detection complexity is not very accurate, as I talked with the staffs in Codility.
  Reply
Badri says:
January 22, 2015 at 6:48 pm
Here’s a more pythonic solution: https://codility.com/demo/results/demoFZ6NPU-CB4/
Reply
- Sheng says:
  January 24, 2015 at 1:44 am
  Thanks for sharing!
  Reply
Pavel says:
April 7, 2015 at 6:21 am
It’s my C# solution (with checking arithmetic overflow) https://codility.com/demo/results/demoHD6J7S-YWT/
Reply
- Sheng says:
  April 7, 2015 at 11:42 pm
  Thanks for sharing!
  Reply
- Mikhail Manukhin says:
  February 15, 2016 at 3:44 am
  Pavel,
  Your solution fails for input: [-2147483648, -2147483648]
  Array A is sorted in non-decreasing order, i.e. not necessarily in increasing.
  Reply
  - Sheng says:
    February 15, 2016 at 4:53 pm
    Thanks for figuring out!
    Reply
Kerem Tubluk says:
April 4, 2016 at 11:03 pm
Well not a solution according to what the lesson teaches but it does the job well and has not that many lines of code; https://codility.com/demo/results/trainingJMCVQ4-Q53/
Reply
- Sheng says:
  April 5, 2016 at 6:54 pm
  You do not need to convert set to list to use len() function.
  Reply
  - Jeffrey Coho says:
    July 11, 2016 at 9:45 pm
    Correct me if I’m wrong but I think he converted to a set to only capture distinct elements
    Reply
    - Sheng says:
      July 19, 2016 at 10:05 pm
      Yes. But before the convert and in the for loop, (s)he transfers all input to their absolute values.
      Reply

def solutionAbsDistinct(A):

size = len(A)

front, end, last, count = 0, size - 1, None, 0

while front < end:

if abs(A[front]) >= abs(A[end]):

last = abs(A[front])

front += 1

else:

last = abs(A[end])

end -= 1

while front < size and abs(A[front]) == last:

front += 1

while end > -1 and abs(A[end]) == last:

end -= 1

count += 1

if front == end and last != abs(A[front]):

count += 1

return count

Dan says:
March 5, 2017 at 5:15 am
In python, this is a one-liner:
1
2
def solution(A):
return len(set((abs(x) for x in A)))

https://codility.com/demo/results/trainingHTA3X8-WDA/
Reply
Tony Sun says:
April 4, 2017 at 5:44 am
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.
Reply

C# solution,

using System;

using System.Collections.Generic;

using System.Collections;

using System.Linq;

// you can also use other imports, for example:

// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.

// Console.WriteLine("this is a debug message");

class Solution {

public int solution(int[] A) {

// write your code in C# 6.0 with .NET 4.5 (Mono)

int len = A.Length;

//int[] B = A[len];

if(len == 1) return 1;

if(len == 0) return -1;

for(int i=0;i<len;i++)

{

if(A[i]<0)

A[i]=0-A[i];

}

int[] B = A.Distinct().ToArray();

return B.Length;

}

C++

#include <cstdlib>

int solution(vector<int> &A){

int L{0}, R{(int)A.size() - 1}, count{0};

while(L <= R){

long abs_L = abs((long)A[L]);

long abs_R = abs((long)A[R]);

if(abs_L >= abs_R){

do{

++L;

} while(abs(A[L]) == abs_L);

}

if(abs_R >= abs_L){

do{

--R;

} while(abs(A[R]) == abs_R);

}

++ count;

}

return count;

}

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.

def solution(arr):

left_idx = 0

right_idx = len(arr) - 1

curr_max = max(abs(arr[0]), abs(arr[-1]))

distinct_count = 1

while left_idx <= right_idx:

left_max = abs(arr[left_idx])

right_max = abs(arr[right_idx])

if left_max == curr_max:

left_idx += 1

continue

if right_max == curr_max:

right_idx -= 1

continue

curr_max = max(left_max, right_max)

distinct_count += 1

return distinct_count

This is a simpler solution with 100 percent score::

def solution(A):

# write your code in Python 3.6

A.sort()

if A[0]<0:

i=0

while i<len(A) and A[i]<0:

A[i]=A[i]*-1

i+=1

A=list(set(A))

return len(A)

C# Code

using System.Linq;

using System;

public static int AbsDistinct(int[] A)

{

var B = from n in A select (long)(Math.Sign(n) * (long)n);

return B.Distinct().ToArray().Length;

}

public static int AbsDistinct(int[] A)

{

HashSet result = new HashSet();

for (int i = 0; i < A.Length; i++)

{

long nArVal = A[i];

long nSign = (long)Math.Sign(nArVal);

long absVal = nSign * nArVal;

result.Add(absVal);

}

return result.Count;

}

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.

#include <climits>

int solution(const std::vector<int> &A) {

int result = 1;

const int N = A.size();

int index_head = 0;

int index_tail = N - 1;

// avoiding INT_MIN in the begininig

while (A[index_head] == INT_MIN) {

index_head++;

}

if (index_head > 0) {

result++;

}

int current = std::max(abs(A[index_head]), abs(A[index_tail]));

// using the cartepillar method

while(index_head <= index_tail) {

int former = abs(A[index_head]);

if (former == current) {

index_head++;

continue;

}

int latter = abs(A[index_tail]);

if (latter == current) {

index_tail--;

continue;

}

if (former >= latter) {

current = former;

index_head++;

} else {

current = latter;

index_tail--;

}

result++;

}

return result;

}

int main() {

std::cout << solution({-5, -3, -1, 0, 3, 6}) << " should be " << 5 << "\n";

std::cout << solution({INT_MIN, -5, -3, -1, 0, 3, 6}) << " should be " << 6 << "\n";

std::cout << solution({INT_MIN, INT_MIN, -5, -3, -1, 0, 3, 6}) << " should be " << 6 << "\n";

std::cout << solution({-5, -3, -1, 0, 3, 6, INT_MAX}) << " should be " << 6 << "\n";

std::cout << solution({-5, -3, -1, 0, 3, 6, INT_MAX, INT_MAX}) << " should be " << 6 << "\n";

std::cout << solution({INT_MIN, -5, -3, -1, 0, 3, 6, INT_MAX}) << " should be " << 7 << "\n";

std::cout << solution({INT_MIN, INT_MIN, -5, -3, -1, 0, 3, 6, INT_MAX, INT_MAX}) << " should be " << 7 << "\n";

return 0;

}

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

Leave a Reply to Dan Cancel reply