Solution to Codility lesson4-exercise3 Distinct problem, link to Codility problem and complete solution at the end of the post.

**Definitions:**

** Problem:**Define a function

*solution*with input

*A*, such that

*solution*returns the number of distinct values in array A.

- Expected worst-case time complexity is
*O(N*log(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.**** **

### Analysis:

To solve this problem, first we have to sort *A, *with the array sorted we jut have to visit every element of *A*.

If *A *has no element the result is 0, otherwise we have at least one distinct element.

11 12 13 |
# No elements than result is 0 if N == 0: return 0 |

Since we already counted the first distinct element, now we search for a different one, and every time we find an element that is different from its predecessor we add one to the result.

15 16 17 18 |
# Itetates through A, and for each new value adds one to the result for k in xrange(1, N): if A[k - 1] != A[k]: result += 1 |

Visiting every element of *A *gives us a time complexity of* O(N)**. *The sort function in Python gives us O(N*log(N))

Then the total time complexity will be *O(N) + O(N*log(N)), *which is *O(N*log(N))*.

For the space complexity we have *O(1)*.

**Complete Solution:**

123456789101112131415161718192021
# Name: Distinct# Link: https://codility.com/demo/take-sample-test/distinct/ def solution(A): N = len(A) result = 1 A.sort() # No elements than result is 0 if N == 0: return 0 # Itetates through A, and for each new value adds one to the result for k in xrange(1, N): if A[k - 1] != A[k]: result += 1 return result

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
# Name: Distinct # Link: https://codility.com/demo/take-sample-test/distinct/ def solution(A): N = len(A) result = 1 A.sort() # No elements than result is 0 if N == 0: return 0 # Itetates through A, and for each new value adds one to the result for k in xrange(1, N): if A[k - 1] != A[k]: result += 1 return result |

*Time Complexity O(N *log(N))*

*Space Complexity O(1)*