Expected number of cluster of cars formed on infinite Road

0 0 3 minutes read

Given an array speed[] of size N denoting the speed of N cars moving on an infinitely long single lane road (i.e. no overtaking is allowed) from left to right. Initially, the rightmost car is at the first position and whenever a car with higher speed reaches a car with lower speed they start moving with the speed to the slower car and form a cluster. The task is to find the total number of clusters that will form.

Note: A single car is also considered a cluster.

Examples:

Input: speed[] = {1, 4, 5, 2, 17, 4 }
Output: 3
Explanation: After a certain time, car with speed 17 will reach car with speed 4(car5) and will form a cluster.
And similarly, cars with speed 4 and 5 will start moving with speed 2 on reaching car3.
The clusters will be (car0), (car1, car2, car3), (car4, car5).

Input: speed[] = {2, 3, 4, 7, 7}
Output: 5
Explanation: Each car will form a cluster.

Approach: The solution is based on greedy approach. Here, a car with less speed forms a cluster with all the cars behind it and having speeds greater than itself. Follow the steps below to solve the problem:

Start iterating from the last index of array speed[].
Store the speed of the car in a variable, say currentCar.
A cluster is formed till the speed of cars behind the currentCar is greater than itself. Therefore increase the value of clusters as soon as a car with less speed is found behind it or when the array is out of bounds.

Below is the implementation of the above approach.

C++

// C++ code to implement above approach
#include <bits/stdc++.h>
#include <vector>
using namespace std;
 
// Function to count total number of clusters
int countClusters(vector<int>& speed)
{
    int N = speed.size();
     
    // For number of clusters
    int cluster = 0;
 
    for (int i = N - 1; i >= 0; i--) {
        int currentCar = speed[i];
         
        // comparing with previous car
        while (i != 0 and speed[i - 1] 
               > currentCar) {
            i--;
        }
        cluster++;
    }
    return cluster;
}
 
// Driver code
int main()
{
    vector<int> speed = { 1, 4, 5, 2, 17, 4 };
    int clusters = countClusters(speed);
    cout << clusters;
    return 0;
}

Java

// Java program to implement
// the above approach
import java.io.*;
class GFG
{
 
  // Function to count total number of clusters
  static int countClusters(int []speed)
  {
    int N = speed.length;
 
    // For number of clusters
    int cluster = 0;
 
    for (int i = N - 1; i >= 0; i--) {
      int currentCar = speed[i];
 
      // comparing with previous car
      while (i != 0 && speed[i - 1] 
             > currentCar) {
        i--;
      }
      cluster++;
    }
    return cluster;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int []speed = { 1, 4, 5, 2, 17, 4 };
    int clusters = countClusters(speed);
    System.out.println(clusters);
 
  }
}
 
// This code is contributed by Saurabh Jaiswal

Python3

# Python code to implement above approach
 
# Function to count total number of clusters
def countClusters(speed):
    N = len(speed)
    clusters = 0
    i = N-1
    while(i >= 0):
        currentCar = speed[i]
        while(i != 0 and speed[i-1] > currentCar):
            i = i-1
        clusters = clusters+1
        i = i-1
    return clusters
 
# Driver code
if __name__ == '__main__':
    speed = [1, 4, 5, 2, 17, 4]
    clusters = countClusters(speed)
    print(clusters)

C#

// C# program to implement
// the above approach
using System;
class GFG
{
 
  // Function to count total number of clusters
  static int countClusters(int []speed)
  {
    int N = speed.Length;
 
    // For number of clusters
    int cluster = 0;
 
    for (int i = N - 1; i >= 0; i--) {
      int currentCar = speed[i];
 
      // comparing with previous car
      while (i != 0 && speed[i - 1] 
             > currentCar) {
        i--;
      }
      cluster++;
    }
    return cluster;
  }
 
  // Driver Code
  public static void Main()
  {
    int []speed = { 1, 4, 5, 2, 17, 4 };
    int clusters = countClusters(speed);
    Console.Write(clusters);
 
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
       // JavaScript code for the above approach 
 
       // Function to count total number of clusters
       function countClusters(speed) {
           let N = speed.length;
 
           // For number of clusters
           let cluster = 0;
 
           for (let i = N - 1; i >= 0; i--) {
               let currentCar = speed[i];
 
               // comparing with previous car
               while (i != 0 && speed[i - 1]
                   > currentCar) {
                   i--;
               }
               cluster++;
           }
           return cluster;
       }
 
       // Driver code
 
       let speed = [1, 4, 5, 2, 17, 4];
       let clusters = countClusters(speed);
       document.write(clusters);
 
 // This code is contributed by Potta Lokesh
   </script>

Output

Time Complexity: O(N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!