This is the Java Program to Solve the passing Car Codility Problem.

Given a boolean array of 0’s and 1’s, where 0’s represent cars going to east and 1’s represent cars going to the west.

Find out the pairs of the cars that will cross each other, that is, the pairs of cars going in another direction.

Example:

ArrayOne = [1, 0, 1, 1, 0, 0, 1, 0]

Output

5

Explanation:

The last 0 has no 1 following it, so their will be no car pairs crossing each other.

The 0’s at positions 5 and 6, have a 1 following them, so there will be two car pairs crossing each other.

The 0 at position 2, have three 1’s following it, so there will be 3 car pairs crossing each other.

So, total 5 car pairs are crossing each other.

**Traverse from the right end of the array** and count the number of 1’s encountered, whenever a 0 is encountered, add the number of 1’s obtained till that point to the number of pairs and continue traversing.

Here is the source code of the Java Program to Solve the passing Car Codility Problem. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

`// Java Program to Solve the passing Car Codility Problem`

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class CarsCodilityProblem {

`// Function to count the number of pairs`

static int passingPairs(int[] array){

int pairs=0;

int count=0;

int i;

for(i = array.length-1; i>=0; i--){

if(array[i] == 1)

`{`

`count++;`

`}`

else{

pairs+=count;

`}`

`}`

return pairs;

`}`

`// Function to read input and display the output`

public static void main(String[] args) {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int size;

System.out.println("Enter the size of the array");

try {

size = Integer.parseInt(br.readLine());

} catch (Exception e) {

System.out.println("Invalid Input");

return;

`}`

int[] array = new int[size];

System.out.println("Enter the binary array elements only 0 and 1");

int i;

for (i = 0; i < array.length; i++) {

try {

array[i] = Integer.parseInt(br.readLine());

} catch (Exception e) {

System.out.println("An error Occurred");

`}`

`}`

int noOfPairs = passingPairs(array);

System.out.println("The number of car pairs passing each other are "

+ noOfPairs);

`}`

`}`

1. In function passingPairs(), the variable pairs and count are initialized to zero.

2. The loop for(i = array.length-1; i>=0; i–) traverses the array from right to left.

3. The condition if(array[i] == 1) counts the number of 1’s encountered till present.

4. The else part, indicating the value zero, adds the number of 1’s encountered to the pairs, since these car pairs are travelling in the opposite direction.

5. The pairs variable is returned.

**Time Complexity: O(n)** where n is the number of elements in the array.

Case 1 (Simple Test Case): Enter the size of the array 8 Enter the binary array elements only 0 and 1 1 0 1 1 0 0 1 0 The number of car pairs passing each other are 5 Case 2 (Simple Test Case - sorted array) : Enter the size of the array 6 Enter the binary array elements only 0 and 1 0 0 0 1 1 1 The number of car pairs passing each other are 9 Case 3 (Simple Test Case - reverse sorted array): Enter the size of the array 4 Enter the binary array elements only 0 and 1 1 1 0 0 The number of car pairs passing each other are 0

**Sanfoundry Global Education & Learning Series – Java Programs.**

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Check Programming Books
- Apply for Computer Science Internship
- Apply for Java Internship
- Check Java Books
- Practice Programming MCQs