Bike Racing – GeeksforGeeks

A motorbike race is being organised with N bikers. The preliminary velocity and the acceleration of the bikers are given in arrays H[] and A[] respectively. A biker whose velocity is L or extra is taken into account to be a quick biker. The whole velocity on the monitor for each hour is calculated by including the velocity of every quick biker in that hour. When the overall velocity on the monitor is M km/hour or extra, the protection alarm activates. The duty is to search out the minimal variety of hours after which the protection alarm will activate.

Examples:

Enter: N = 3, M = 400, L = 120, H = {20, 50, 20}, A = {20, 70, 90}
Output: 3
Clarification: Speeds of all of the Bikers after each hour ranging from 0
Biker1 = [20  40  60  80 100] 
Biker2 = [50 120 190 260 330]
Biker3 = [20 110 200 290 380]
Preliminary Pace on monitor  = 0 
as a result of not one of the biker’s velocity is quick sufficient.
Pace on monitor after 1st Hour= 120
Pace on monitor after 2nd Hour= 190+200=390
Pace on monitor after third Hour= 260+290=550
The Alarm will begin at third Hour.

Enter: N = 2, M = 60, L = 120, H = {50, 30}, A = {20, 40}
Output: 2

Naive Method: A easy method is to calculate the velocity of each Bike in each Hour ranging from the 0^th hour. When the overall velocity on the monitor is not less than M km/hr, that’s the minimal time when the alarm will activate.

Time Complexity: O(N * max(L, M))
Auxiliary Area: O(1)

Environment friendly Method: The issue could be solved with the assistance of the Binary Search primarily based on the next commentary: 

It may be noticed that if in i^th hour complete velocity on the monitor is larger than or equal to M then in (i+1)^th hour it is going to additionally fulfill the situation because the velocity of Bikes are growing linearly with time.

Observe the steps talked about under to implement the above thought:

• Discover the utmost and minimal required hours to activate the alarm as a result of they are going to be used as the acute values for the binary search.
• The utmost and minimal values might be max(L, M) and 0 respectively.
• Use the binary search over this time vary and in every iteration do the next:
  • Iterate from i = 0 to N:
    • Discover the velocity of the biker at the moment.
    • If the velocity of the biker at the moment is not less than L then add his velocity to the velocity of the monitor.
  • If the velocity of the monitor is not less than M then search on the left half of the time vary. In any other case, search on the suitable half.
• Return the minimal time as the reply.

Under is the implementation of the above method.

Time Complexity: O(N * log(max(L, M)))
Auxiliary Area: O(1)