Tasks Details
easy
1.
PassingCars
Count the number of passing cars on the road.
Task Score
100%
Correctness
100%
Performance
100%
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:
function 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.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used JavaScript
Time spent on task 27 minutes
Notes
not defined yet
Task timeline
Code: 10:48:38 UTC,
js,
verify,
result: Failed
Analysis
expand all
Example tests
1.
0.163 s
WRONG ANSWER,
got 6 expected 5
Code: 10:50:52 UTC,
js,
verify,
result: Passed
Analysis
Code: 10:51:38 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var east = 0, west = 0;
for(var i=0;i<A.length;i++){
if(A[i]) west ++;
else east ++;
}
return east+west;
}
User test case 1:
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]
Analysis
Code: 10:52:45 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var east = 0, west = 0;
for(var i=0;i<A.length;i++){
if(A[i]) west ++;
else east ++;
}
return east*west-1;
}
User test case 1:
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]
Analysis
Code: 10:59:52 UTC,
js,
verify,
result: Failed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var pass=0, west = 0;
for(var i=0;i<A.length;i++){
if(A[i] === 0) pass += west;
else west ++;
if(pass > 1e9) return -1;
}
return pass;
}
User test case 1:
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]
Analysis
expand all
Example tests
1.
0.155 s
WRONG ANSWER,
got 1 expected 5
Code: 11:03:17 UTC,
js,
verify,
result: Failed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var zCount = 0; // how many going east
var passing = 0; // total passing pairs
for(var i =0;i< A.length;i++){
if(i == 1){
passing += zCount;
}
else zCount++;
}
if(passing > 1e9 || passing < 0) return -1;
else return passing;
}
User test case 1:
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]
Analysis
expand all
Example tests
1.
0.159 s
WRONG ANSWER,
got 1 expected 5
Code: 11:05:10 UTC,
js,
verify,
result: Failed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var east = 0; passing = 0;
for(var i = 0; i< A.length; i++){
if(i == 1){
passing += east;
}
else east++;
}
if(passing > 1e9 || passing < 0) return -1;
else return passing;
}
User test case 1:
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]
Analysis
expand all
Example tests
1.
0.164 s
WRONG ANSWER,
got 1 expected 5
Code: 11:06:04 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var east = 0; passing = 0;
for(var i = 0; i< A.length; i++){
if(A[i] == 1){
passing += east;
}
else east++;
}
if(passing > 1e9 || passing < 0) return -1;
else return passing;
}
User test case 1:
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]
Analysis
Code: 11:06:40 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var east = 0; passing = 0;
for(var i = 0; i< A.length; i++){
if(A[i] == 1){
passing += east;
if(passing > 1e9) return -1;
}
else east++;
}
return passing;
}
User test case 1:
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]
Analysis
Code: 11:06:47 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var east = 0; passing = 0;
for(var i = 0; i< A.length; i++){
if(A[i] == 1){
passing += east;
if(passing > 1e9) return -1;
}
else east++;
}
return passing;
}
User test case 1:
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]
User test case 2:
[0, 0]
Analysis
Code: 11:06:55 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var east = 0; passing = 0;
for(var i = 0; i< A.length; i++){
if(A[i] == 1){
passing += east;
if(passing > 1e9) return -1;
}
else east++;
}
return passing;
}
User test case 1:
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]
User test case 2:
[0, 0]
User test case 3:
[1, 1]
Analysis
expand all
User tests
1.
0.164 s
OK
function result: 51
function result: 51
1.
0.158 s
OK
function result: 0
function result: 0
1.
0.158 s
OK
function result: 0
function result: 0
Code: 11:07:16 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var east = 0; passing = 0;
for(var i = 0; i< A.length; i++){
if(A[i] == 1){
passing += east;
if(passing > 1e9) return -1;
}
else east++;
}
return passing;
}
User test case 1:
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]
User test case 2:
[0, 0]
User test case 3:
[1, 1]
User test case 4:
[1, 1, 1, 1, 1, 1, 0]
Analysis
expand all
User tests
1.
0.174 s
OK
function result: 51
function result: 51
1.
0.157 s
OK
function result: 0
function result: 0
1.
0.162 s
OK
function result: 0
function result: 0
1.
0.170 s
OK
function result: 0
function result: 0
Code: 11:07:29 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var east = 0; passing = 0;
for(var i = 0; i< A.length; i++){
if(A[i] == 1){
passing += east;
if(passing > 1e9) return -1;
}
else east++;
}
return passing;
}
User test case 1:
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]
User test case 2:
[0, 0]
User test case 3:
[1, 1]
User test case 4:
[1, 1, 1, 1, 1, 1, 0]
User test case 5:
[0, 1, 1, 1, 1, 1, 1, 1]
Analysis
Code: 11:08:56 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var east = 0; passing = 0;
for(var i = 0; i< A.length; i++){
if(A[i] == 1){
passing += east; // pair only count (0,1)
if(passing > 1e9) return -1;
}
else east++; // increasing numbers of car go to east (0)
}
return passing;
}
User test case 1:
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]
User test case 2:
[0, 0]
User test case 3:
[1, 1]
User test case 4:
[1, 1, 1, 1, 1, 1, 0]
User test case 5:
[0, 1, 1, 1, 1, 1, 1, 1]
Analysis
Code: 11:09:01 UTC,
js,
final,
score:
100
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var east = 0; passing = 0;
for(var i = 0; i< A.length; i++){
if(A[i] == 1){
passing += east; // pair only count (0,1)
if(passing > 1e9) return -1;
}
else east++; // increasing numbers of car go to east (0)
}
return passing;
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.160 s
OK
2.
0.163 s
OK
1.
0.166 s
OK
2.
0.162 s
OK
3.
0.162 s
OK
4.
0.165 s
OK
1.
0.163 s
OK
1.
0.162 s
OK
1.
0.165 s
OK
expand all
Performance tests
1.
0.175 s
OK
1.
0.205 s
OK
1.
0.208 s
OK
2.
0.196 s
OK
1.
0.206 s
OK
2.
0.203 s
OK
1.
0.203 s
OK
2.
0.208 s
OK
3.
0.203 s
OK