Anish and Cars

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
12 upvotes

Problem statement

Anish has brought N cars and organized a race among the cars. The ith car starts in a unique position POSITION[i] and has a unique speed SPEED[i]. Every car starts driving at the same time after the gun is fired and stops at the point of destination D. However, this competition has a unique rule: no car can overtake any other car. Find the number of unique arriving times of the car.

Example:- 
Let, 

N = 5
TARGET = 12
POSITION = [10, 8, 0, 5, 3]
SPEED = [2, 4, 1, 1, 3]

Answer:- 3 ( Car 1 and 2 arrive at the same time, car 3 arrives at a different time, car 4 and car 5 arrive at a different time, so there is a total of 3 different arrival times).

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of each test case contains an integer ‘N’ and ‘D’ denoting the number of cars and the point of destination respectively.

The next line of every test case contains ‘N’ integers containing the POSITIONS of the ith car.

The next line of every test case contains ‘N’ integers containing the SPEEDS of the ith car.
Output Format : 
For each test case, print an integer denoting the number of unique arrivals of the cars.

The output of each test case should be printed in a separate line.
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 5
1 <= N <= 10^5
1 <= D <= 10^6
1 <= POSITIONS[i] <= 10^6
1 <= SPEED[i] <= 10^6  

Note:- The positions of the cars are pairwise distinct.

Time Limit: 1 sec
Sample Input 1 :
2
1 10
3
3
4 10
4 3 2 1
4 3 2 1
Sample Output 1 :
1
4
Explanation for Sample Output 1 :
In the first test case, the answer should be 1 because there is only one car and so there is 1 unique arrival time.
In the second test case, the answer should be 4 because every car arrives at a different time.
Sample Input 2 :
1
2 10
6 8 
3 2
Sample Output 2 :
2
Hint

Check whether a particular car can overtake any other car in front.

Approaches (1)
Greedy

Approach:-

 

We can observe that if a car can overtake any car in front then it will arrive with that car and will not have a unique arrival time. So we check whether a particular car can overtake any car (i.e if the time required by that car is less than the time taken by the cars in front of it) in front or not. If yes, we increase the count else not.

 

Algorithm:-

 

  1. Initialize a variable named ANS to store the number of distinct arrival times.
  2. Sort the cars according to the distance they have to cover.
  3. Initialize a variable named M with 0 to store the maximum time required by the cars to reach the destination
  4. Iterate from 0 to N. (Let’s say the iterator is i).
    1. Initialize a variable named T and update it to ( D - POSITION[i] ) / SPEED[i]
    2. If T is less than equal to M, continue.
    3. Else, update M to T and increment ANS by 1.
  5. Return ANS.
Time Complexity

O(N log N), where N is the number of cars.

We are iterating over the cars once after sorting the array, so the time complexity is O(N log N).

Space Complexity

O(N), where N is the number of cars.

We are using an auxiliary array to sort the cars according to the distance they have to cover, so the space complexity is O(N).

Code Solution
(100% EXP penalty)
Anish and Cars
Full screen
Console