CODEWITHSUNDEEP
javaalgorithm
redandblue
redandblue

Reputation: 770

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?

Upvotes: 20

Views: 47337

Answers (15)

Nazariy Vlizlo
Nazariy Vlizlo

Reputation: 977

For this task I developed 2 solution 1st one:

public func solution(_ A : inout [Int]) -> Int {
    var counter = 0
    var result = 0

    for i in 0..<A.count {
        if A[i] == 1 {
            result += counter
        } else {
            counter += 1
        }

        guard result <= 1_000_000_000 else { return -1 }
    }

    return result
}

The 2nd solution using Prefix Sums:

public func solution(_ A : inout [Int]) -> Int {
    var p = Array(repeating: 0, count: A.count + 1)
    var result = 0

    for i in 1..<A.count + 1 {
        p[i] = p[i - 1] + A[i - 1]
    }

    for i in 0..<A.count {
        if A[i] == 0 {
            result += p[p.count - 1] - p[i + 1]
        }

        guard result <= 1_000_000_000 else { return -1 }
    }

    return result
}

Thanks

Upvotes: 0

MD. Shafayatul Haque
MD. Shafayatul Haque

Reputation: 998

Got 100% score with PHP.

function solution($A) {
    // Implement your solution here
    $cnt = 0;
    $output = 0;
    foreach($A as $k=>$v){
        if($v==0){
            $cnt++;
        }else{
            $output += $cnt;
            if($output > 1000000000){
                return -1;
            }
        }
    }

    return $output;
}

Upvotes: 0

sm7
sm7

Reputation: 669

100% score, correctness and performance and O(n) complexity. Ref.

Overall idea is to traverse the array only once and on the way whenever you encounter one (1), increase the counter by number of zeros (0) encountered so far.

public int solution(int[] A) {
  int count = 0;

  int numZero = 0;
  for (int i=0; i < A.length; i++) {
      if ((A[i] == 1 && numZero == 0)) continue; // optional step

      if (A[i] == 0) numZero++;
      if (A[i] == 1) {
          count += numZero;
      }

      if (count > 1000000000) return -1;
  }

  return count;
}

Upvotes: 0

Ahmed Ghazey
Ahmed Ghazey

Reputation: 489

  class Solution {
           public int solution(int[] A) {
            int count = 0;
            int p = 0;
            int [] suffix = new int [A.length];
            while (p < A.length && A[p] == 1) p++;
            if (p == A.length) return 0;
            suffix[suffix.length-1] = A[A.length-1];
            for (int i =  A.length-2; i >= p; i--){
                suffix[i] = suffix[i+1] + A[i];
            }
    
            for (int i = p; i < suffix.length; i++){
                if (A[i] == 0){
                    count+= suffix[i];
                    if (count >1000_000_000 )
                        return -1;
                }
            }
    
    
    
            return count;
        }
}

Upvotes: 0

hoangn
hoangn

Reputation: 21

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.

Upvotes: 0

Ľuboš Pilka
Ľuboš Pilka

Reputation: 1148

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. enter image description here

Upvotes: 41

Amin
Amin

Reputation: 138

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;
    }
}

Upvotes: 2

Nirav Chhatrola
Nirav Chhatrola

Reputation: 512

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.

Upvotes: 1

Droid Teahouse
Droid Teahouse

Reputation: 1013

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;
 }

Upvotes: 3

iamdimitar
iamdimitar

Reputation: 174

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;
}

Upvotes: 8

Koin Arab
Koin Arab

Reputation: 1107

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;
}

Upvotes: 11

Tanel
Tanel

Reputation: 213

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;
    }
}

Upvotes: 16

tas
tas

Reputation: 35

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

Upvotes: -1

user3662248
user3662248

Reputation: 149

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;
}

Upvotes: 14

Kromster
Kromster

Reputation: 7397

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:

  1. Imagine array 0..N

  2. Take element X (iterate from 0 to Nth element)

  3. If value of element X is 0 then count how many 1 elements it has on the right

  4. If value of element X is 1 then count how many 0 elements it has on left

  5. Repeat for next X

  6. 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.

Upvotes: 10

Related Questions