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