Solution to Codility lesson3-exercise2 Passing Cars problem, link to Codility problem and complete solution at the end of the post.
Definitions:
Pair: A pair can be described by a tuple
, such that
;
Problem:
Define a function solution with input A, such that solution returns the numbers of pairs in array A. If the count is greater than 1,000,000,000 return -1.
- Expected worst-case time complexity is O(N);
- Expected worst-case space complexity is O(1);
Elements of input arrays can be modified.
Analysis:
The strategy to solve this problem is, for each car going east or number 0, we add 1 to our counter for cars going east.
11 12 13 |
# Count the numbers of cars going if A[k] == 0: count_zero += 1 |
And for each car going west or number 1 we add the number of cars going east until this moment to the result.
14 15 16 |
# For each car coming add the numbers of cars going before else: result += count_zero |
To complete this task, we have to visit every element of A, so the total Time Complexity is O(N).
For the space complexity we have O(1) since we have no variable depending on the size input.
Complete Solution:
12345678910111213141516171819202122
# Name: PassingCars# Link: https://codility.com/demo/take-sample-test/passing_cars/ def solution(A): N = len(A) result = 0 count_zero = 0 for k in xrange(N): # Count the numbers of cars going if A[k] == 0: count_zero += 1 # For each car coming add the numbers of cars going before else: result += count_zero # -1 if result over 1,000,000,000 if result > 1000000000: return -1 return result
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
# Name: PassingCars # Link: https://codility.com/demo/take-sample-test/passing_cars/ def solution(A): N = len(A) result = 0 count_zero = 0 for k in xrange(N): # Count the numbers of cars going if A[k] == 0: count_zero += 1 # For each car coming add the numbers of cars going before else: result += count_zero # -1 if result over 1,000,000,000 if result > 1000000000: return -1 return result |
Time Complexity O(N)
Space Complexity O(1)