Mr. Henrys Gas Station Problem - Natwest Online Assessment IIT BHU

Problem Preview

"Mr. Henry is saving money to buy a new car. His old car gets **low gas mileage**. Moreover, its fuel efficiency has diminished over time. Presently, it takes **one gallon of gasoline to travel one mile**. He needs to drive to his office, which is at a distance **D** from his home. On his way to the office, there are **N** gas stations. Each gas station can only sell a specific amount of gasoline (in gallons) based on a government limit. *(Assume that in order to keep running, the car must always have some gasoline in it at all times.)* Write an algorithm to help Mr. Henry determine the **minimum number of gas stations** at which he should stop to successfully reach his office. If it is **not possible** to reach the office, output **-1**. --- ## Input Format 1. The first line contains an integer **num**, representing the number of gas stations (**N**). 2. The second line contains **N** space-separated integers **dis1 dis2 ... disN**, where **disi** represents the distance of the **i-th** gas station from Mr. Henry's home. 3. The third line contains an integer **numS**, representing the number of gas stations available (**numS = N**). 4. The fourth line contains **N** space-separated integers **iGas1 iGas2 ... iGasN**, where **iGasi** represents the gallons of gasoline available at the **i-th** gas station. 5. The next line contains an integer **distance**, representing the distance of the office from Mr. Henry's home (**D**). 6. The next line contains an integer **initialGas**, representing the initial amount of gasoline in the car (**K**). --- ## Output Format Print a single integer representing the **minimum number of gas stations** at which Mr. Henry should stop to successfully reach his office. If reaching the office is impossible, print **-1**. --- ## Constraints * (1 <= N <= 10^4) * (1 <= dis_i < D <= 10^5) * (1 <= iGas_i <=10^3) * (0 <= initialGas <=10^5) --- ## Example ### Input ``` 4 5 7 8 10 4 2 3 15 15 15 5 ``` ### Output ``` 3 ``` ### Explanation * Initially, the car has **5 gallons**, allowing it to travel **5 miles**, reaching the **1st gas station**. * Refuel there with **2 gallons**. * Later, the car reaches the **2nd gas station** and refuels with **3 gallons**. * Finally, it reaches the **3rd gas station**, where it refuels with **15 gallons**, which is enough to reach the office. Thus, the minimum number of gas stations visited is: ``` 3 ```"