You are ready to travel long distance by road for Spring break to visit your family. Assume that an array called distances[] already has the distance to each gas station along the way in sorted order. For convenience, index 0 has the starting position, even though it is not a gas station. We also know the range of the car, that is, the max distance the car can travel with a full-tank of gas (ignore "reserve"). You are starting the trip with a full tank as well. Now, your goal is to minimize the total gas cost. There is another parallel array prices[] that contains the gas price per gallon for each gas station, to help you! Since index 0 is not a gas station, we will indicate very high price for gas so that it won't be accidentally considered as gas station. BTW, it is OK to reach your final destination with minimal gas, but do not run out of gas along the way! Program needs to output # of gas stops to achieve the minimum total gas cost.

double distances[], prices[];
double range;
int numStations; //# of gas stations - index goes from 1 to numStations in distances[] & prices[] arrays
//find # of gas stops you need to make to go from distances[currentIndex] to destDistance
int gasStops(int currentIndex, double destDistance)
Let us look at an example. Let us say you need to travel 450 miles & the range is 210 miles.

distances[] = { 0, 100, 200, 300, 400, 500}; //5 gas stations
prices[] = {100, 2.10, 2.20, 2.30, 2.40, 2.50}; //100 is dummy entry for the initial position - it is not a gas station
Since gas price continues to increase along the way, we will keep refilling at the first 3 stations then we can dash to the destination for the final 150 miles - no need to stop at gas station at 400 or 500 miles. So, the answer will be 3 stations.

Let us consider another configuration with just price changes.

prices[] = {100, 2.50, 2.40, 2.30, 2.20, 2.10};
Since the gas price continues to decrease along the way, we will fill "just enough" gas to reach the next station, right? So, we will use all 4 stations (last gas station is beyond the destination). Answer will be 4 stations.

Let us consider one more configuration with price changes.

prices[] = {100, 2.60, 2.10, 2.40, 2.15, 2.20};
We will reach the station at 200 miles ($2.10 per gallon) since it is the cheapest one $2.10 per gallon. We will fill the tank fully and dash to gas station at 400 miles with $2.15 per gallon - fill as much gas as we need to reach the destination - Just 2 gas stops!