'Codility passing car - how to approach this problem
A non-empty zero-indexed 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] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty zero-indexed array A of N integers, returns the number of passing cars.
The function should return −1 if the number 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] = 1
the function should return 5, as explained above.
Assume that:
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.
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
I don't understand why there are five passing cars, instead of 6. Why doesn't (2,1) count as a passing car? Can someone provide some explanation on how to approach this problem?
Solution 1:[1]
You need to count number of cars passings. Cars are positioned on the road as input says and start driving into either one of directions. When car drives, we can easily see that it will drive by cars moving in the opposite direction, but only if they were in front of it. Essentially that can be formulated as:
Imagine array 0..N
Take element X (iterate from 0 to Nth element)
If value of element X is 0 then count how many 1 elements it has on the right
If value of element X is 1 then count how many 0 elements it has on left
Repeat for next X
Sum up and divide by 2 (cos it takes 2 cars to pass each other), that's the answer.
In case with 0 1 0 1 1 we have 3+1+2+2+2 = 10. Divide by 2 = 5 passings.
We don't count pair 2-1 because 2nd car is driving to the East and never passes the 1st car that is driving away from it to the West.
Solution 2:[2]
Most of the answers here just provided algorithms to solve the task but not answering author original question. "Why is there only 5 pairs of car and not 6 ?" That is because cars (2,1) never pass each other.
Here is quick visualization of problem.
Solution 3:[3]
Here is my code that got 100% in C#
class Solution
{
public int solution(int[] A)
{
int count = 0;
int multiply = 0;
foreach (int car in A)
{
if (car == 0)
{
multiply = multiply + 1;
}
if (multiply > 0)
{
if (car == 1)
{
count = count + multiply;
if (count > 1000000000)
{
return -1;
}
}
}
}
return count;
}
}
Solution 4:[4]
Time Complexity - O(n) Space Complexity - O(1) The logic I came up with goes like this.
- Have 2 variables. Count and IncrementVal. Initialize both to zero.
- Traverse through the array. Every time you find a 0, increment the IncrementVal.
- Every time you find a 1, modify count by adding the incrementVal to count.
- After the array traversal is completed, return back the count.
Note:: Example code provided below assumes static array and a predefined array size. You can make it dynamic using vectors.
#include <iostream>
using namespace std;
int getPass(int* A, int N)
{
unsigned long count = 0;
int incrementVal = 0;
for(int i = 0; i < N; i++)
{
if(A[i]==0)
{
incrementVal++;
}
else if (A[i]==1)
{
count = count + incrementVal;
}
if(count > 1000000000) return -1;
}
return count;
}
int main()
{
int A[]={0,1,0,1,1};
int size = 5;
int numPasses = getPass(A,size);
cout << "Number of Passes: " << numPasses << endl;
}
Solution 5:[5]
This is simple example in Java. I think it should be passed on 100%
public int solution(int[] A) {
int countOfZeros = 0, count = 0;
for (int i = 0; i < A.length; i++){
if (A[i] == 0) countOfZeros++;
if (A[i] == 1) count += countOfZeros;
if (count > 1000000000) return -1;
}
return count;
}
Solution 6:[6]
100% JavaScript. The logic behind is that each West car (1) creates a pair with all of the preceding East cars (0). Hence, every time we get a 1 we add all the preceding 0s.
function solution(A) {
var zeroesCount = 0; //keeps track of zeroes
var pairs = 0; //aka the result
for (var i=0; i<A.length; i++) {
A[i]===0 ? zeroesCount++ : pairs += zeroesCount; //count 0s or add to answer when we encounter 1s
if (pairs > 1000000000 ) { //required by the question
return -1;
}
}
return pairs;
}
Solution 7:[7]
To answer the original question it states in the problem:
0 ? P < Q < N
For all pairs (P,Q) P must come before Q. 2 does not come before 1.
You can also work from the end, accumulating 1's to match with the next 0:
public int solution(int[] A) {
int ones =0, count=0;
for (int j = A.length-1; j >=0; j--) {
if (A[j] ==1) {
ones++;
} else if (A[j] ==0) {
count+=ones;
}
if ( count > 1_000_000_000) {
return -1;
}
}
return count;
}
Solution 8:[8]
I know I am very late for this answer. Though I am giving my solution that's having 100% correctness and performance on codility.
public int solution(int[] A) {
int A1 = 0;
int pair = 0;
for(int i = A.length-1 ; i>=0; i--){
if(A[i]==1){
A1++;
}else{
pair += A1;
}
if(pair > 1000000000){
return -1;
}
}
return pair;
}
The approach I have followed is as bellow,
iterate array from last element to first element (reverse)
increase count until you are getting 1
when you found 0 add your count of 1's to countPair.
at the end of iteration of array countPair is your answer.
Solution 9:[9]
We are seeking for pair of cars (P, Q), where 0 ? P < Q < N.
Your case (2,1) , does not pass the requirement.
My approach is simple. for each 1 value, we have to count previous zeroes.
My code got 100% in JAVA with time complexity O(n):
class Solution {
public int solution(int[] A) {
int count = 0;
int zeroCount = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] == 0) {
zeroCount++;
} else if (A[i] == 1) {
count += zeroCount;
}
}
return count >= 0 && count <= 1000_000_000 ? count : -1;
}
}
Solution 10:[10]
I had the same problem with OP.
Why there are five passing cars, instead of 6. Why doesn't (2,1) count as a passing car?
Because in the question:
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.
Means the index of P must < index of Q. And P value must be 0 to be counted. In this case (2,1), then index of P(2) > Q(1) => wrong.
Solution 11:[11]
We need only to traverse the Zeros, in order to find the number of total crossings.
No need to run extra code for Ones, because the number of crossings for every Zero we check, is equal to the number of crossings we get, when we check all Ones for that particular Zero.
public class passingCars {
public static void main(String[] args) {
int k;
int cnt = 0;
// Test array
int[] A = { 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1 };
for (int i = 0; i < A.length; i++) {
if (A[i] == 0) {
k = i + 1;
while (k < A.length) {
if (A[k] == 1) {
cnt++;
}
k++;
}
}
}
System.out.println(cnt);
}
}
result: 17
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow