A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.
Array A contains only 0s and/or 1s:
- 0 represents a car traveling east,
- 1 represents a car traveling west.
The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.
For example, consider array A such that:
A[0] = 0 A[1] = 1 A[2] = 0 A[3] = 1 A[4] = 1We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
Write a function:
def solution(A)
that, given a non-empty array A of N integers, returns the number of pairs of passing cars.
The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.
For example, given:
A[0] = 0 A[1] = 1 A[2] = 0 A[3] = 1 A[4] = 1the function should return 5, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of array A is an integer that can have one of the following values: 0, 1.
def solution(A):
"""
https://app.codility.com/demo/results/training3K95ND-KGH/
100%
Idea-
Before - we can just use two loops and for each zero count number of 1 in second loop big o n2
But lets use prefix some to do it in linear time-
As per question explanation we have to find the total pairs of ones with zeros towards east direction ie. right to left
In order to find that we can use prefix some ie.
prefix_sum = for any index it represents the total number of cars, which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
So what we do is - First find the # first_car_crosses_max - this is the first car which crosses all the cars to right/ moving to east of it
Now for each car(zero/0) moving car we have to do first_car_crosses_max - prefix_sum[index] why we do see below-
Why? The prefix sum for this index is the number of cars which are to the left side and for sure they will not pass current index car
so we subtract all of these cars and we found the only cars which are moving to east direction passing all others cars. At this point we are
100 % sure that all cars(1) must be passed by this car by definition of first_car_crosses_max
See below- assume moving cars only in east direction, since given in question 0 ≤ P < Q < N so just assume that west car moving is still
west<<<<<------>>>>>>>east
0->>> travels east(passes 3 cars) 1 0->>> travels east(passes 2 cars) 1 1
0 1 0 1 1
for first zero do prefix some if current is 1 add with previous value
0 1 1 2 3
Problem-
consider array A such that:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
"""
print("Input " + str(A))
ar_length = len(A)
# prefix_sum - for any index it represents the total number of cars which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
prefix_sum = [0] * (ar_length + 1)
for i in range(1, ar_length + 1):
prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
num_passing_cars = 0
print("prefix_sum " + str(prefix_sum))
# first_car_crosses_max - this is the first car which crosses all the cars to right of it
first_car_crosses_max = prefix_sum[ar_length]
print("first_car_crosses_max " + str(first_car_crosses_max))
for index, car in enumerate(A):
# 0 represents a car traveling east and we have to find the passing cars for zero so that we can find the total number of pairs/crossings
if car == 0:
print("")
print("Can not pass cars " + str(prefix_sum[index]))
print("Can pass car at current index " + str(first_car_crosses_max - prefix_sum[index]))
# just subtract from max so we get the total cars passing at this point
num_passing_cars += (first_car_crosses_max - prefix_sum[index])
print("Index " + str(index))
print("Total num_passing_cars " + str(num_passing_cars))
# 10 ** 9 = 1000,000,000, exit for boundary condition as given in question
if num_passing_cars > 10 ** 9:
return -1
return num_passing_cars
def solution(A):
"""
https://app.codility.com/demo/results/training3K95ND-KGH/
100%
Idea-
Before - we can just use two loops and for each zero count number of 1 in second loop big o n2
But lets use prefix some to do it in linear time-
As per question explanation we have to find the total pairs of ones with zeros towards east direction ie. right to left
In order to find that we can use prefix some ie.
prefix_sum = for any index it represents the total number of cars, which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
So what we do is - First find the # first_car_crosses_max - this is the first car which crosses all the cars to right/ moving to east of it
Now for each car(zero/0) moving car we have to do first_car_crosses_max - prefix_sum[index] why we do see below-
Why? The prefix sum for this index is the number of cars which are to the left side and for sure they will not pass current index car
so we subtract all of these cars and we found the only cars which are moving to east direction passing all others cars. At this point we are
100 % sure that all cars(1) must be passed by this car by definition of first_car_crosses_max
See below- assume moving cars only in east direction, since given in question 0 ≤ P < Q < N so just assume that west car moving is still
west<<<<<------>>>>>>>east
0->>> travels east(passes 3 cars) 1 0->>> travels east(passes 2 cars) 1 1
0 1 0 1 1
for first zero do prefix some if current is 1 add with previous value
0 1 1 2 3
Problem-
consider array A such that:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
"""
#print("Input " + str(A))
ar_length = len(A)
# prefix_sum - for any index it represents the total number of cars which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
prefix_sum = [0] * (ar_length + 1)
for i in range(1, ar_length + 1):
prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
num_passing_cars = 0
#print("prefix_sum " + str(prefix_sum))
# first_car_crosses_max - this is the first car which crosses all the cars to right of it
first_car_crosses_max = prefix_sum[ar_length]
#print("first_car_crosses_max " + str(first_car_crosses_max))
for index, car in enumerate(A):
# 0 represents a car traveling east and we have to find the passing cars for zero so that we can find the total number of pairs/crossings
if car == 0:
#print("")
#print("Can not pass cars " + str(prefix_sum[index]))
#print("Can pass car at current index " + str(first_car_crosses_max - prefix_sum[index]))
# just subtract from max so we get the total cars passing at this point
num_passing_cars += (first_car_crosses_max - prefix_sum[index])
#print("Index " + str(index))
#print("Total num_passing_cars " + str(num_passing_cars))
# 10 ** 9 = 1000,000,000, exit for boundary condition as given in question
if num_passing_cars > 10 ** 9:
return -1
return num_passing_cars
def solution(A):
"""
https://app.codility.com/demo/results/training3K95ND-KGH/
100%
Idea-
Before - we can just use two loops and for each zero count number of 1 in second loop big o n2
But lets use prefix some to do it in linear time-
As per question explanation we have to find the total pairs of ones with zeros towards east direction ie. right to left
In order to find that we can use prefix some ie.
prefix_sum = for any index it represents the total number of cars, which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
So what we do is - First find the # first_car_crosses_max - this is the first car which crosses all the cars to right/ moving to east of it
Now for each car(zero/0) moving car we have to do first_car_crosses_max - prefix_sum[index] why we do see below-
Why? The prefix sum for this index is the number of cars which are to the left side and for sure they will not pass current index car
so we subtract all of these cars and we found the only cars which are moving to east direction passing all others cars. At this point we are
100 % sure that all cars(1) must be passed by this car by definition of first_car_crosses_max
See below- assume moving cars only in east direction, since given in question 0 ≤ P < Q < N so just assume that west car moving is still
west<<<<<------>>>>>>>east
0->>> travels east(passes 3 cars) 1 0->>> travels east(passes 2 cars) 1 1
0 1 0 1 1
for first zero do prefix some if current is 1 add with previous value
0 1 1 2 3
Problem-
consider array A such that:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
"""
#print("Input " + str(A))
ar_length = len(A)
# prefix_sum - for any index it represents the total number of cars which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
prefix_sum = [0] * (ar_length + 1)
for i in range(1, ar_length + 1):
prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
num_passing_cars = 0
#print("prefix_sum " + str(prefix_sum))
# first_car_crosses_max - this is the first car which crosses all the cars to right of it
first_car_crosses_max = prefix_sum[ar_length]
#print("first_car_crosses_max " + str(first_car_crosses_max))
for index, car in enumerate(A):
# 0 represents a car traveling east and we have to find the passing cars for zero so that we can find the total number of pairs/crossings
if car == 0:
#print("")
#print("Can not pass cars " + str(prefix_sum[index]))
#print("Can pass car at current index " + str(first_car_crosses_max - prefix_sum[index]))
# just subtract from max so we get the total cars passing at this point
num_passing_cars += (first_car_crosses_max - prefix_sum[index])
#print("Index " + str(index))
#print("Total num_passing_cars " + str(num_passing_cars))
# 10 ** 9 = 1000,000,000, exit for boundary condition as given in question
if num_passing_cars > 10 ** 9:
return -1
return num_passing_cars
def solution(A):
"""
100%
Idea-
Before - we can just use two loops and for each zero count number of 1 in second loop big o n2
But lets use prefix some to do it in linear time-
As per question explanation we have to find the total pairs of ones with zeros towards east direction ie. right to left
In order to find that we can use prefix some ie.
prefix_sum = for any index it represents the total number of cars, which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
So what we do is - First find the # first_car_crosses_max - this is the first car which crosses all the cars to right/ moving to east of it
Now for each car(zero/0) moving car we have to do first_car_crosses_max - prefix_sum[index] why we do see below-
Why? The prefix sum for this index is the number of cars which are to the left side and for sure they will not pass current index car
so we subtract all of these cars and we found the only cars which are moving to east direction passing all others cars. At this point we are
100 % sure that all cars(1) must be passed by this car by definition of first_car_crosses_max
See below- assume moving cars only in east direction, since given in question 0 ≤ P < Q < N so just assume that west car moving is still
west<<<<<------>>>>>>>east
0->>> travels east(passes 3 cars) 1 0->>> travels east(passes 2 cars) 1 1
0 1 0 1 1
for first zero do prefix some if current is 1 add with previous value
0 1 1 2 3
Problem-
consider array A such that:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
"""
#print("Input " + str(A))
ar_length = len(A)
# prefix_sum - for any index it represents the total number of cars which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
prefix_sum = [0] * (ar_length + 1)
for i in range(1, ar_length + 1):
prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
num_passing_cars = 0
#print("prefix_sum " + str(prefix_sum))
# first_car_crosses_max - this is the first car which crosses all the cars to right of it
first_car_crosses_max = prefix_sum[ar_length]
#print("first_car_crosses_max " + str(first_car_crosses_max))
for index, car in enumerate(A):
# 0 represents a car traveling east and we have to find the passing cars for zero so that we can find the total number of pairs/crossings
if car == 0:
#print("")
#print("Can not pass cars " + str(prefix_sum[index]))
#print("Can pass car at current index " + str(first_car_crosses_max - prefix_sum[index]))
# just subtract from max so we get the total cars passing at this point
num_passing_cars += (first_car_crosses_max - prefix_sum[index])
#print("Index " + str(index))
#print("Total num_passing_cars " + str(num_passing_cars))
# 10 ** 9 = 1000,000,000, exit for boundary condition as given in question
if num_passing_cars > 10 ** 9:
return -1
return num_passing_cars
def solution(A):
"""
100%
Idea-
Before - we can just use two loops and for each zero count number of 1 in second loop big o n2
But lets use prefix some to do it in linear time-
As per question explanation we have to find the total pairs of ones with zeros towards east direction ie. right to left
In order to find that we can use prefix some ie.
prefix_sum = for any index it represents the total number of cars, which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
So what we do is - First find the # first_car_crosses_max - this is the first car which crosses all the cars to right/ moving to east of it
Now for each car(zero/0) moving car we have to do first_car_crosses_max - prefix_sum[index] why we do see below-
Why? The prefix sum for this index is the number of cars which are to the left side and for sure they will not pass current index car
so we subtract all of these cars and we found the only cars which are moving to east direction passing all others cars. At this point we are
100 % sure that all cars(1) must be passed by this car by definition of first_car_crosses_max
See below- assume moving cars only in east direction, since given in question 0 ≤ P < Q < N so just assume that west car moving is still
west<<<<<------>>>>>>>east
0->>> travels east(passes 3 cars) 1 0->>> travels east(passes 2 cars) 1 1
0 1 0 1 1
for first zero do prefix some if current is 1 add with previous value
0 1 1 2 3
Problem-
consider array A such that:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
"""
#print("Input " + str(A))
ar_length = len(A)
# prefix_sum - for any index it represents the total number of cars which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
prefix_sum = [0] * (ar_length + 1)
for i in range(1, ar_length + 1):
prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
num_passing_cars = 0
#print("prefix_sum " + str(prefix_sum))
# first_car_crosses_max - this is the first car which crosses all the cars to right of it
first_car_crosses_max = prefix_sum[ar_length]
#print("first_car_crosses_max " + str(first_car_crosses_max))
for index, car in enumerate(A):
# 0 represents a car traveling east and we have to find the passing cars for zero so that we can find the total number of pairs/crossings
if car == 0:
#print("")
#print("Can not pass cars " + str(prefix_sum[index]))
#print("Can pass car at current index " + str(first_car_crosses_max - prefix_sum[index]))
# just subtract from max so we get the total cars passing at this point
num_passing_cars += (first_car_crosses_max - prefix_sum[index])
#print("Index " + str(index))
#print("Total num_passing_cars " + str(num_passing_cars))
# 10 ** 9 = 1000,000,000, exit for boundary condition as given in question
if num_passing_cars > 10 ** 9:
return -1
return num_passing_cars
def solution(A):
"""
Idea-
Before - we can just use two loops and for each zero count number of 1 in second loop big o n2
But lets use prefix some to do it in linear time-
As per question explanation we have to find the total pairs of ones with zeros towards east direction ie. right to left
In order to find that we can use prefix some ie.
prefix_sum = for any index it represents the total number of cars, which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
So what we do is - First find the # first_car_crosses_max - this is the first car which crosses all the cars to right/ moving to east of it
Now for each car(zero/0) moving car we have to do first_car_crosses_max - prefix_sum[index] why we do see below-
Why? The prefix sum for this index is the number of cars which are to the left side and for sure they will not pass current index car
so we subtract all of these cars and we found the only cars which are moving to east direction passing all others cars. At this point we are
100 % sure that all cars(1) must be passed by this car by definition of first_car_crosses_max
See below- assume moving cars only in east direction, since given in question 0 ≤ P < Q < N so just assume that west car moving is still
west<<<<<------>>>>>>>east
0->>> travels east(passes 3 cars) 1 0->>> travels east(passes 2 cars) 1 1
0 1 0 1 1
for first zero do prefix some if current is 1 add with previous value
0 1 1 2 3
Problem-
consider array A such that:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
"""
#print("Input " + str(A))
ar_length = len(A)
# prefix_sum - for any index it represents the total number of cars which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
prefix_sum = [0] * (ar_length + 1)
for i in range(1, ar_length + 1):
prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
num_passing_cars = 0
#print("prefix_sum " + str(prefix_sum))
# first_car_crosses_max - this is the first car which crosses all the cars to right of it
first_car_crosses_max = prefix_sum[ar_length]
#print("first_car_crosses_max " + str(first_car_crosses_max))
for index, car in enumerate(A):
# 0 represents a car traveling east and we have to find the passing cars for zero so that we can find the total number of pairs/crossings
if car == 0:
#print("")
#print("Can not pass cars " + str(prefix_sum[index]))
#print("Can pass car at current index " + str(first_car_crosses_max - prefix_sum[index]))
# just subtract from max so we get the total cars passing at this point
num_passing_cars += (first_car_crosses_max - prefix_sum[index])
#print("Index " + str(index))
#print("Total num_passing_cars " + str(num_passing_cars))
# 10 ** 9 = 1000,000,000, exit for boundary condition as given in question
if num_passing_cars > 10 ** 9:
return -1
return num_passing_cars
def solution(A):
"""
Idea-
Before - we can just use two loops and for each zero count number of 1 in second loop big o n2
But lets use prefix some to do it in linear time-
As per question explanation we have to find the total pairs of ones with zeros towards east direction ie. right to left
In order to find that we can use prefix some ie.
prefix_sum = for any index it represents the total number of cars, which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
So what we do is - First find the # first_car_crosses_max - this is the first car which crosses all the cars to right/ moving to east of it
Now for each car(zero/0) moving car we have to do first_car_crosses_max - prefix_sum[index] why we do see below-
Why? The prefix sum for this index is the number of cars which are to the left side and for sure they will not pass current index car
so we subtract all of these cars and we found the only cars which are moving to east direction passing all others cars. At this point we are
100 % sure that all cars(1) must be passed by this car by definition of first_car_crosses_max
See below- assume moving cars only in east direction, since given in question 0 ≤ P < Q < N so just assume that west car moving is still
west<<<<<------>>>>>>>east
0->>> travels east(passes 3 cars) 1 0->>> travels east(passes 2 cars) 1 1
0 1 0 1 1
for first zero do prefix some if current is 1 add with previous value
0 1 1 2 3
Problem-
consider array A such that:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
"""
#print("Input " + str(A))
ar_length = len(A)
# prefix_sum - for any index it represents the total number of cars which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
prefix_sum = [0] * (ar_length + 1)
for i in range(1, ar_length + 1):
prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
num_passing_cars = 0
#print("prefix_sum " + str(prefix_sum))
# first_car_crosses_max - this is the first car which crosses all the cars to right of it
first_car_crosses_max = prefix_sum[ar_length]
#print("first_car_crosses_max " + str(first_car_crosses_max))
for index, car in enumerate(A):
# 0 represents a car traveling east and we have to find the passing cars for zero so that we can find the total number of pairs/crossings
if car == 0:
#print("")
#print("Can not pass cars " + str(prefix_sum[index]))
#print("Can pass car at current index " + str(first_car_crosses_max - prefix_sum[index]))
# just subtract from max so we get the total cars passing at this point
num_passing_cars += (first_car_crosses_max - prefix_sum[index])
#print("Index " + str(index))
#print("Total num_passing_cars " + str(num_passing_cars))
# 10 ** 9 = 1000,000,000, exit for boundary condition as given in question
if num_passing_cars > 10 ** 9:
return -1
return num_passing_cars
def solution(A):
"""
Idea-
Before - we can just use two loops and for each zero count number of 1 in second loop big o n2
But lets use prefix some to do it in linear time-
As per question explanation we have to find the total pairs of ones with zeros towards east direction ie. right to left
In order to find that we can use prefix some ie.
prefix_sum = for any index it represents the total number of cars, which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
So what we do is - First find the # first_car_crosses_max - this is the first car which crosses all the cars to right/ moving to east of it
Now for each car(zero/0) moving car we have to do first_car_crosses_max - prefix_sum[index] why we do see below-
Why? The prefix sum for this index is the number of cars which are to the left side and for sure they will not pass current index car
so we subtract all of these cars and we found the only cars which are moving to east direction passing all others cars. At this point we are
100 % sure that all cars(1) must be passed by this car by definition of first_car_crosses_max
See below- assume moving cars only in east direction, since given in question 0 ≤ P < Q < N so just assume that west car moving is still
west<<<<<------>>>>>>>east
0->>> travels east(passes 3 cars) 1 0->>> travels east(passes 2 cars) 1 1
0 1 0 1 1
for first zero do prefix some if current is 1 add with previous value
0 1 1 2 3
Problem-
consider array A such that:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
"""
#print("Input " + str(A))
ar_length = len(A)
# prefix_sum - for any index it represents the total number of cars which can not pass to any of its right side cars
# reason is only east moving car can pass to other cars as per problem statement
prefix_sum = [0] * (ar_length + 1)
for i in range(1, ar_length + 1):
prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
num_passing_cars = 0
#print("prefix_sum " + str(prefix_sum))
# first_car_crosses_max - this is the first car which crosses all the cars to right of it
first_car_crosses_max = prefix_sum[ar_length]
#print("first_car_crosses_max " + str(first_car_crosses_max))
for index, car in enumerate(A):
# 0 represents a car traveling east and we have to find the passing cars for zero so that we can find the total number of pairs/crossings
if car == 0:
#print("")
#print("Can not pass cars " + str(prefix_sum[index]))
#print("Can pass car at current index " + str(first_car_crosses_max - prefix_sum[index]))
# just subtract from max so we get the total cars passing at this point
num_passing_cars += (first_car_crosses_max - prefix_sum[index])
#print("Index " + str(index))
#print("Total num_passing_cars " + str(num_passing_cars))
# 10 ** 9 = 1000,000,000, exit for boundary condition as given in question
if num_passing_cars > 10 ** 9:
return -1
return num_passing_cars
The solution obtained perfect score.