Home/Questions/Q 803895
Next
In Process

Quearn Latest Questions

codemania
  • 0
codemania
Asked: May 27, 20232023-05-27T09:40:41+00:00 2023-05-27T09:40:41+00:00In:

Codility Passing Car Problem in Java

  • 0
Codility Passing Car Problem in Java
codejava
Share

    1 Answer

    1. codemania
      codemania
      2023-05-27T09:41:04+00:00Added an answer on May 27, 2023 at 9:41 am

      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.

      2. // Java Program to Solve the passing Car Codility Problem
      3. import java.io.BufferedReader;
      4. import java.io.InputStreamReader;
      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
      • 0
    You must login to add an answer.
    Need An Account, 
    Related Questions