Ninja And Stops
Ninja wants to travel from his house to a given destination, which is ‘X’ miles from his house. Along the way, he needs to fill gas in his vehicle. He knows there are ‘Y’ stations in his way. He also knows the distance between the station and his house, and how many liters of gas that particular station has.

Ninja starts his journey, with an infinite capacity of the tank filled with ‘Z’ liters of starting fuel. Suppose his vehicle uses 1 liter of gas for every mile, and ninja can stop at any gas station, transfer all the available gas at that station and then move ahead.

Now, you need to find out what is the minimum number of stops Ninja must make to reach his desired destination.

Note:

Note that if Ninja reaches a particular stop with no fuel, it can still fill his tank at that stop and continue his journey ahead. Similarly, if he reaches his destination with no fuel, it is still considered to have arrived.

For example :

Given X = 10, Y = 4, ARR[Y] = {[1, 6], [2, 3], [3, 3], [6, 4]} and Z = 1 So the path followed in this case would look like this: Ninja starts with 1L of gas. Drives to the first gas station at position 1, using 1L of gas, then refueling with 6L of gas. Then, drive to position 6, using 5L of gas, then refueling 4L in the current 1L of gas, making it a total of 5L of gas. Finally, drive to the destination consuming 4L of gas. So, Ninja made 2 refueling stops before reaching the destination. So, you need to print 2.

Input Format:

The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows. The first line of each test case contains three space-separated integers ‘X’, ‘Y’ and ‘Z’, denoting distance in miles, number of gas stations, and starting fuel of the vehicle. The next ‘Y’ lines of each test contain an array of ‘Y’ pairs where each pair denotes the distance from the house and available fuel for a refill.

Output Format:

For each test case, you need to return a single integer denoting the minimum stops made to reach the destination. Print the output of each test case in a separate line.

Note:

You don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints:

1

Question

Ninja And Stops

Ninja wants to travel from his house to a given destination, which is ‘X’ miles from his house. Along the way, he needs to fill gas in his vehicle. He knows there are ‘Y’ stations in his way. He also knows the distance between the station and his house, and how many liters of gas that particular station has.

Ninja starts his journey, with an infinite capacity of the tank filled with ‘Z’ liters of starting fuel. Suppose his vehicle uses 1 liter of gas for every mile, and ninja can stop at any gas station, transfer all the available gas at that station and then move ahead.

Now, you need to find out what is the minimum number of stops Ninja must make to reach his desired destination.

Note:

Note that if Ninja reaches a particular stop with no fuel, it can still fill his tank at that stop and continue his journey ahead. Similarly, if he reaches his destination with no fuel, it is still considered to have arrived.

For example :

Given X = 10, Y = 4, ARR[Y] = {[1, 6], [2, 3], [3, 3], [6, 4]} and Z = 1
So the path followed in this case would look like this:

Ninja starts with 1L of gas. 
Drives to the first gas station at position 1, using 1L of gas, then refueling with 6L of gas.
Then, drive to position 6, using 5L of gas, then refueling 4L in the current 1L of gas, making it a total of 5L of gas.
Finally, drive to the destination consuming 4L of gas.
So, Ninja made 2 refueling stops before reaching the destination. So, you need to print 2.

Input Format:

The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains three space-separated integers ‘X’, ‘Y’ and ‘Z’, denoting distance in miles, number of gas stations, and starting fuel of the vehicle.

The next ‘Y’ lines of each test contain an array of ‘Y’ pairs where each pair denotes the distance from the house and available fuel for a refill.

Output Format:

For each test case, you need to return a single integer denoting the minimum stops made to reach the destination.

Print the output of each test case in a separate line.

Note:

You don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= X, Z  <= 10^7
0 <= size of Y <= 10^5
1 <= Y1, Y2 <= 10^7

Time limit: 1 sec

Accepted Answer

Recursion

The simple idea that we use in this approach will be to check all the available paths. For this we create a recursive function let’s say MINIMUM_STOP_HELPER() that will return the desired path. The function will take fuel left, distance travelled, next gas station, and the array of all the stations as its parameters.

The base conditions for this recursive function will be:

If you have enough fuel
If you have reached the target
If no stations left and you did not reach the target
If you cannot reach the next fuel station with the current fuel.

Algorithm:

Create the recursive function.
Base Cases:
- If you have enough fuel to reach destination from start
  - Return 0
- If you have reached the target
  - Return 0
- If no stations left and you did not reach the target
  - Return -1
- If you cannot reach the next fuel station with the current fuel.
  - Return -1
For the main function:
- Find minimum of the two cases:
  - If you refill at the next station.
  - If you do not refill at the next station.

Space Complexity: O(n)Explanation:

O(N), where N is the number of stations.

The space required for recursive stack is O(N), so the overall complexity will be O(N).

Time Complexity: O(2^n)Explanation:

O(2 ^ N), where N is the number of stations.

For every station, the function will perform two cases, if fuel refilled and if fuel is not filled. Hence the overall time complexity of this approach is O(2 ^ N).

Accepted Answer

Dynamic Programming

In this approach, we will use a DP array that will store the farthest distance we can get using “INDEX” number of refuelling stops, where “INDEX” is the position at which it is stored in the DP array. Finally, we will get the smallest “INDEX” for which DP[INDEX] is greater than or equal to our destination.

Algorithm:

The base case is that you can travel ‘Z’ distance without stopping anywhere. ‘Z’ here is the fuel that we have at the start.
Now, iterating through stops:
- Update the DP[INDEX + 1] :
  - If we can reach let’s say “ith” station using “INDEX” stops, then we can possibly reach DP[INDEX] + (fuel at station i) using “INDEX + 1” stops.
  - Using this logic update DP[INDEX + 1].
Finally iterate through the DP array and find an index when:
- DP[INDEX] >= ‘X’:
  - Return INDEX
- Else:
  - Return -1

Space Complexity: O(n)Explanation:

O(N), where N is the number of stations.

The space required for a DP array is O(N), so the overall complexity will be O(N)

Time Complexity: O(n^2)Explanation:

O(N * N), where N is the number of stations.

For every station, the function will have to traverse through all stations ahead of it in order to update the DP array. Hence the overall time complexity of this approach is O(N * N).

Python (3.5)

'''
	Time complexity: O(N * N) 
	Space complexity: O(N)

    Where N is the number of stations.
'''

def minRefuelStops(target, startFuel, stations):
    
    # Base condition.
    if startFuel > target:
        
        return 0
        
    # Initialise variable to store number of station.
    n = len(stations)
    
    # Initialise current fuel as start fuel.
    currFuel = startFuel
    
    # Create a dp array.
    dp = []
    for i in range(n + 1):
        dp.append(0)
        
    # The dp[i] => Max distance that can be travelled with i stops.
    dp[0] = currFuel
    
    # Start traversing.
    for i in range(n):
        
        for j in range(i, -1, -1):
            
            if dp[j] >= stations[i][0]:
                
                dp[j + 1] = max(dp[j + 1], dp[j] + stations[i][1])
            
            else:
                
                break
            
    # Traverse again.
    for i in range(n + 1):
        
        # If curr value of dp becomes more than target meaning we reached the destination.
        if dp[i] >= target:
            
            return i
            
    # Else return -1.
    return -1

Java (SE 1.8)

/*

	Time complexity: O(N * N) 

	Space complexity: O(N)



	Where N is the number of stations.

*/



import java.util.ArrayList;



public class Solution {



	public static int minRefuelStops(int target, int startFuel, ArrayList> stations) {



		// Base condition.

		if (startFuel > target) {

			return 0;

		}



		// Initialise variable to store number of station.

		int n = stations.size();



		// Initialise current fuel as start fuel.

		int currFuel = startFuel;



		// Create a dp array.

		ArrayList dp = new ArrayList();

		for (int i = 0; i < n + 1; i++) {

			dp.add((long) 0);

		}



		// The dp[i] => Max distance that can be travelled with i stops.

		dp.set(0, (long) currFuel);



		// Start traversing.s

		for (int i = 0; i < n; i++) {

			for (int j = i; j >= 0; j--) {

				if (dp.get(j).intValue() >= stations.get(i).get(0).intValue()) {

					dp.set(j + 1, Math.max(dp.get(j + 1), dp.get(j) + stations.get(i).get(1)));

				} else {

					break;

				}

			}

		}



		// Traverse again.

		for (int i = 0; i <= n; i++) {



			// If curr value of dp becomes more than target meaning we reached the destination.

			if (dp.get(i) >= target) {

				return i;

			}

		}



		// Else return -1.

		return -1;

	}

}

C++ (g++ 5.4)

/*

	Time complexity: O(N * N) 

	Space complexity: O(N)



	Where N is the number of stations.

*/



#include



int minRefuelStops(int target, int startFuel, vector>& stations) 

{



    // Base condition.

    if(startFuel > target)

    {

        return 0;

    }

    

    // Initialise variable to store number of station.

    int n = stations.size();



    // Initialise current fuel as start fuel.

    int currFuel = startFuel;



    // Create a dp array.

    vector dp(n + 1, 0);

		

    // The dp[i] => Max distance that can be travelled with i stops.

	dp[0] = currFuel;



    // Start traversing.

    for(int i = 0; i < n; i++)

    {

        for(int j = i; j >= 0; j--)

        {

            if(dp[j] >= stations[i][0])

            {

                dp[j + 1] = max(dp[j + 1], dp[j] + stations[i][1]);

            }

            else

            { 

                break;

            }    

        }

    }



    // Traverse again.

    for(int i = 0; i <= n; i++)

    {



        // If curr value of dp becomes more than target meaning we reached the destination.

        if(dp[i] >= target)

        {

            return i;

        }

    }

    

    // Else return -1.

    return -1;

}

Accepted Answer

Priority Queue (Max Heap) Approach

In this approach, the basic idea that we will use is that we will refuel the vehicle only when the need arises. There are just two cases when we are required to fill:

When we will not be able to reach the next station.
When we have gone past all the stations and are short on fuel to reach our destination.

Whenever one of the above two cases arrive, we search for the fuel station that we have passed till now, and have the maximum fuel, and if that station can not provide us enough fuel to reach the next station or the destination, then we will be required to refuel again using the same procedure.

Algorithm:

Create a max heap priority queue, that will store the capacity of each gas station we have passed.
When we reach a station with negative fuel, meaning we don’t have enough fuel to reach there:
- Search for the max heap for the gas station with the maximum capacity that we have passed.
If at any point we are not able to reach the next station or our destination by passing through all the stations before that, meaning if at any time the above process fails:
- We can not reach the destination at any cost
  - Return -1
We keep a track of all the stops we made and return it finally if we reach the destination.

Space Complexity: O(n)Explanation:

O(N), where N is the number of stations.

The space required for the priority queue is O(N), so the overall complexity will be O(N).

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), where N is the number of stations.

We iterate through all the stations making complexity O(N), and the push and pop operation on the stations takes O(log(N)) time. Hence the overall time complexity of this approach is O(N * log(N)).

Python (3.5)

'''
	Time complexity: O(N * logN) 
	Space complexity: O(N)

    Where N is the number of stations.
'''

import heapq

def minRefuelStops(target, startFuel, stations):

    # Check for the base condition.
    if target <= startFuel:
        
        return 0
        
    # Initialise a priority queue.
    
    pq = []
    
    # initialise current fuel as start fuel.
    currFuel = startFuel
    
    # Initialise variable to store the count of stops.
    ans = 0
    
    # Initialise variable to store previous value.
    prev = 0
    
    # Start traversing
    for i in range(len(stations)):
        
        # Initialise variable to store capacity and location.
        capacity = stations[i][1]
        location = stations[i][0]
        
        # Update current fuel.
        currFuel = currFuel - (location - prev)
        
        # Start traversing through the queue.
        while len(pq) > 0 and currFuel < 0:
            
            # Update value.
            currFuel = currFuel + (-heapq.heappop(pq))
            
            ans += 1
            
        # If current fuel becomes less than or equal to zero.
        if currFuel < 0:
            
            return -1
            
        # Update previous.
        prev = location
        
        # Push capacity into the queue.
        heapq.heappush(pq, -capacity)
        
    # Update current fuel.
    currFuel = currFuel - (target - prev)
    
    # Start traversing.
    while len(pq) > 0 and currFuel < 0:
        
        # Update current fuel.
        currFuel = currFuel + (-heapq.heappop(pq))
        
        ans += 1
        
    # If current fuel becomes less than or equal to zero.
    if currFuel < 0:
        
        return -1
        
    return ans

Java (SE 1.8)

/*

	Time complexity: O(N * logN) 

	Space complexity: O(N)



	Where N is the number of stations.

*/



import java.util.ArrayList;

import java.util.PriorityQueue;

import java.util.Collections;



public class Solution {

	public static int minRefuelStops(int target, int startFuel, ArrayList> stations) {



		// Check for the base condition.

		if (target <= startFuel) {

			return 0;

		}



		// Initialise a priority queue.

		PriorityQueue pq = new PriorityQueue(Collections.reverseOrder());



		// Initialise current fuel as start fuel.

		int currFuel = startFuel;



		// Initialise variable to store the count of stops.

		int ans = 0;



		// Initialise variable to store previous value.

		int prev = 0;



		// Start traversing.

		for (int i = 0; i < stations.size(); i++) {



			// Initialise variable to store capacity and location.

			int capacity = stations.get(i).get(1);

			int location = stations.get(i).get(0);



			// Update current fuel.

			currFuel = currFuel - (location - prev);



			// Start traversing through the queue.

			while (!pq.isEmpty() && currFuel < 0) {



				// Update value.

				currFuel = currFuel + pq.peek();

				pq.remove();



				// Increment ans.

				ans = ans + 1;

			}



			// If current fuel becomes less than or equal to zero.

			if (currFuel < 0) {



				// Return -1.

				return -1;

			}



			// Update previous.

			prev = location;



			// Push capacity into the queue.

			pq.add(capacity);

		}



		// Update current fuel.

		currFuel = currFuel - (target - prev);



		// Start traversing.

		while (!pq.isEmpty() && currFuel < 0) {



			// Update current fuel.

			currFuel = currFuel + pq.peek();

			pq.remove();



			// Increment ans.

			ans = ans + 1;

		}



		// If current fuel becomes less than or equal to zero.

		if (currFuel < 0) {



			// Return -1.

			return -1;

		}



		// Return ans.

		return ans;

	}

}

C++ (g++ 5.4)

/*

	Time complexity: O(N * logN) 

	Space complexity: O(N)



	Where N is the number of stations.

*/



#include



int minRefuelStops(int target, int startFuel, vector>& stations) 

{



    // Check for the base condition.

    if(target <= startFuel)

    {

        return 0;

    }



    // Initialise a priority queue.

    priority_queue pq;



    // Initialise current fuel as start fuel.

    int currFuel = startFuel;



    // Initialise variable to store the count of stops.

    int ans = 0;



    // Initialise variable to store previous value.

    int prev = 0;



    // Start traversing.

    for(int i = 0; i < stations.size(); i++)

    {



        // Initialise variable to store capacity and location.

        int capacity = stations[i][1];

        int location = stations[i][0];



        // Update current fuel.

        currFuel = currFuel - (location - prev);



        // Start traversing through the queue.

        while(!pq.empty() && currFuel < 0)

        {



            // Update value.

            currFuel = currFuel + pq.top();

            pq.pop();



            // Increment ans.

            ans++;

        }



        // If current fuel becomes less than or equal to zero.

        if(currFuel < 0)

        {



            // Return -1.

            return -1;

        }



        // Update previous.

        prev = location;



        // Push capacity into the queue.

        pq.push(capacity);

    }



    // Update current fuel.

    currFuel = currFuel - (target - prev);

    

    // Start traversing.

    while(!pq.empty() && currFuel < 0)

    {



        // Update current fuel.

        currFuel = currFuel + pq.top();

        pq.pop();



        // Increment ans.

        ans++;

    }



    // If current fuel becomes less than or equal to zero.

    if(currFuel < 0)

    {



        // Return -1.

        return -1;

    }



    // Return ans.

    return ans;

}

Ninja starts his journey, with an infinite capacity of the tank filled with ‘Z’ liters of starting fuel. Suppose his vehicle uses 1 liter of gas for every mile, and ninja can stop at any gas station, transfer all the available gas at that station and then move ahead.

Now, you need to find out what is the minimum number of stops Ninja must make to reach his desired destination.

Note:

For example :

Input Format:

Output Format:

Note:

Constraints:

Top Cognizant Trainee Analyst interview questions & answers

Popular interview questions of Trainee Analyst