Passing Cars (Codility)

Problem Statement: PassingCars

C++ Solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

// you can use includes, for example: #include <algorithm> // you can write to stdout for debugging purposes, e.g. // cout << "this is a debug message" << endl; int solution(vector<int> &A) { // write your code in C++11 (g++ 4.8.2) auto goingEast = 0; auto pairsPassing = 0; for (auto &e : A) { if (e == 0) { goingEast++; } else if (e == 1) { pairsPassing += goingEast; if (pairsPassing > 1000000000) return -1; } } return pairsPassing; }

C# Solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

using System; // you can also use other imports, for example: // using System.Collections.Generic; // you can write to stdout for debugging purposes, e.g. // Console.WriteLine("this is a debug message"); class Solution { public int solution(int[] A) { // write your code in C# 6.0 with .NET 4.5 (Mono) var eastBound = 0; var pairsCrossing = 0; foreach(var car in A) { if(car == 0) { eastBound++; } else if(car == 1) { pairsCrossing += eastBound; if(pairsCrossing > 1000000000) return -1; } } return pairsCrossing; } }

Learnings

• counting number of 1s or west bound cars

My initial idea was to go through the entire array and then count number of west bound cars. Then, traverse the array again and each time a 0 i.e. east bound car is encountered, update the west bound car count. Each time a 1 i.e. west bound car is encountered, simply decrement the count of west bound cars. This approach has one failed test case. I still need to analyze why. After this, however I figured out that it is possible to have a solution without doing an initial pass to find number of west bound cars.