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.

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.

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:

Distinct

Python

# 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)

Link to GitHub solution here .
Link to Codility problem here .