Last Updated: 27 Oct, 2021

Anish and Cars

Moderate

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).

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

Solve now

Approaches

01 Approach

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:-

Initialize a variable named ANS to store the number of distinct arrival times.
Sort the cars according to the distance they have to cover.
Initialize a variable named M with 0 to store the maximum time required by the cars to reach the destination
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.
Return ANS.

Solve now