Solve the passing Car Codility Problem.

Category : Java | Sub Category : Java Programs from Coding Interviews | By Prasad Bonam Last updated: 2020-12-20 14:16:14 Viewed : 446


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

Problem Description

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.

Problem Solution

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.

Program/Source Code

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.

  1.  
  2. // Java Program to Solve the passing Car Codility Problem
  3. import java.io.BufferedReader;
  4. import java.io.InputStreamReader;
  5.  
  6. public class CarsCodilityProblem {
  7.     // Function to count the number of pairs
  8.     static int passingPairs(int[] array){
  9.         int pairs=0;
  10.         int count=0;
  11.         int i;
  12.         for(i = array.length-1; i>=0; i--){
  13.             if(array[i] == 1)
  14.             {
  15.                 count++;
  16.             }
  17.             else{
  18.                 pairs+=count;
  19.             }
  20.         }
  21.         return pairs;
  22.     }
  23.     // Function to read input and display the output
  24.     public static void main(String[] args) {
  25.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  26.         int size;
  27.         System.out.println("Enter the size of the array");
  28.         try {
  29.             size = Integer.parseInt(br.readLine());
  30.         } catch (Exception e) {
  31.             System.out.println("Invalid Input");
  32.             return;
  33.         }
  34.         int[] array = new int[size];
  35.         System.out.println("Enter the binary array elements only 0 and 1");
  36.         int i;
  37.         for (i = 0; i < array.length; i++) {
  38.             try {
  39.                 array[i] = Integer.parseInt(br.readLine());
  40.             } catch (Exception e) {
  41.                 System.out.println("An error Occurred");
  42.             }
  43.         }
  44.         int noOfPairs = passingPairs(array);
  45.         System.out.println("The number of car pairs passing each other are "
  46.                                                                  + noOfPairs);
  47.     }
  48. }
Program Explanation

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.

Runtime Test Cases
 
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

Search
Related Articles

Leave a Comment: