Codility ‘PassingCars’ Solution

Short Problem Definition:

Count the number of passing cars on the road.

Link

PassingCars

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1)

Execution:

Count all cars heading in one direction (west). Each car heading the other direction (east) passes all cars that went west so far. Note that east cars at the beginning of the list pass no cars! Also do not forget the upper limit!

Solution:
def solution(A):
    west_cars = 0
    cnt_passings = 0

    for idx in xrange(len(A)-1, -1, -1):
        if A[idx] == 0:
            cnt_passings += west_cars
            if cnt_passings > 1000000000:
                return -1
        else:
            west_cars += 1

    return cnt_passings

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin