Question

Minimum Recharging Stops
You have decided that your first purchase after graduation will be a Tesla Model X. You have further decided to drive from Harrisburg to San Francisco, as quickly (and safely) as possible. In order to minimize your travel time, you wish to minimize the number of recharging stops. You have recorded the distances between charging stations on your route, and you know the maximum range that you can travel on a single charge.

Input: An array g containing the distances of charging stations on the route from the starting point; r the range you can travel on a single charge, and d the length of the route from Harrisburg to San Francisco. You are guaranteed that the distances between the charging stations will be less than or equal to r.

Return: The minimum number of stops needed for charging in order to complete the trip.

a) Suppose that you wrote an exhaustive search algorithm. How many possible solutions would you examine?
b) Write an efficient algorithm to solve this problem.

Answer 1

1) For exaustive solution, I will examine the boundary conditions and the condition where range is less than the next recharge station.

2)

An algorithm for the peoblem:

#include<iostream>
using namespace std;
int main()
{
   int N=5,i=0;
   int g[N],r,d;
   for(int i=0;i<N;i++)
   {
       cin>>g[i];
   }
   cin>>r>>d;
   int travelled=0;
   while(d>0)
{
   travelled=travelled+g[i];
   if(travelled>r)
   {
       int extra=0;
       extra=travelled-r;
       travelled=travelled-extra;
       cout<<"Recharge"<<endl;
       r=r+r;//increase range
   }
   else
   {
      
       cout<<"Travelling"<<endl;
   }
   d=d-travelled;
   if(d==0 || d<0)
   cout<<"Reached Destination";
}
  
   return 0;
}