Minimum Time to Finish the Race
You are given a 0-indexed 2D integer array tires where tires[i] = [fi, ri] indicates that the i^th tire can finish its x^th successive lap in fi * ri^(x-1) seconds.
- For example, if
fi = 3andri = 2, then the tire would finish its1^stlap in3seconds, its2^ndlap in3 * 2 = 6seconds, its3^rdlap in3 * 2^2 = 12seconds, etc.
You are also given an integer changeTime and an integer numLaps.
The race consists of numLaps laps and you may start the race with any tire. You have an unlimited supply of each tire and after every lap, you may change to any given tire, including the current tire type, if you wait changeTime seconds.
Return the minimum time to finish the race.
Example 1
Input
tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4Output
21Using tire 0 for two laps, changing to a new tire 0, then using it for two more laps takes 2 + 6 + 5 + 2 + 6 = 21 seconds, which is minimum.
Example 2
Input
tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5Output
25Using tire 1 for two laps, changing to a new tire 1 for two more laps, then changing to tire 0 for the final lap takes 25 seconds, which is minimum.
Constraints
- 1 <= tires.length <= 10^5
- tires[i].length == 2
- 1 <= fi, changeTime <= 10^5
- 2 <= ri <= 10^5
- 1 <= numLaps <= 1000
Asked at 1 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.