Last Updated: 17 Oct, 2021
Minimum Stop Required To Reach The Destination
Moderate
Asked in companies
Ninja bought a plane that can cover a distance of at most ‘K’ units in one flight. Now, the ninja wants to show this plane to his best friend, whose house lies at point (X, 0) on the x-axis. There are multiple airports on the x-axis marked by 1. If there is no airport at any point, then it is marked as 0.
Given an integer array ‘AIRPORTS’ of size ‘N’ containing the information about airports on the x-axis, can you find the minimum number of stops that must be taken by the plane to reach the destination (X,0) on the x-axis. If the destination is unreachable, return -1. The plane starts from the origin (0, 0).
For example:
You are given AIRPORTS = [1, 1, 1, 0, 1, 0], ‘K’ = 2 and ‘X’ = 4.
The answer will be 1. The plane makes its first stop at (2, 0) and then reaches the destination (4, 0) in the next fight. Hence the total number of stops is 1.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases.
The first line of each test case contains three space-separated integers, ‘N’, ‘K’, ’X’, representing the length of the ‘AIRPORTS’ array, maximum distance covered by plane in one flight, and destination on the x-axis, respectively.
The second line of each test case contains N space-separated integers, representing the information about the airports on the x-axis.
Output Format:
For each test case, print a single integer, denoting the minimum number of stops that must be taken by the plane to reach the destination (X,0) on the x-axis.
The output of each test case will be printed in a separate line.
Constraints:
1 <= T <= 10
1 <= N <= 5000
1 <= K < N
1 <= X < N
0 <= AIRPORTS[i] <= 1
Time limit: 1 sec
Note:
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Approaches
In this approach, we will find the shortest path to the destination using Breadth-First Search. The starting point will be the origin, and all the airports at a distance at most ‘K’ from any airport ‘A’ will be considered the neighbors of ‘A’.
Algorithm:
- Initialize an empty queue q.
- Initialize a boolean array visited.
- Initialize a variable stops.
- Add 0 to q
- Set visited[0] as true.
- Start BFS. Iterate while q is not empty.
- Get the size of the q and store it in variable size.
- Iterate level in 0 to size
- Get top of the queue and store in a variable curr.
- If curr is equal to x
- return stops - 1
- Set neighbors as (curr + k)
- Increment curr by 1.
- Iterate all neighbors.
- If this neighbor has an airport and if not already visited, add it q and mark it visited.
- Increment curr by 1.
- Increment stops by 1.
- If we reach here, that means the destination was not reached. Return -1.
In this approach, we will divide the problem into smaller sub-problems. We will define dp[i], which will store the minimum number of stops required to reach the destination from point i. Thus, dp[0] will be our final answer.
Algorithm:
- If no airport at destination i.e, airports[x] is 0 return -1.
- Initialize a dp array of size x.
- Iterate i in (x - 1) to 0
- If (i + k) is greater than or equal to x
- Set dp[i] as airports[i] - 1.
- Otherwise, if airports[i] is 1
- Initialize a variable temp with value (i + k).
- Initialize a variable flag with a value false.
- If dp[temp] not equal to -1
- Set flag as true
- Set dp[i] as dp[temp] + 1
- Break.
- Decrement temp by 1
- If dp[temp] not equal to -1
- If flag is false, set dp[i] as -1.
- Otherwise, set dp[i] as -1.
- If (i + k) is greater than or equal to x
- Finally, return dp[0].
In this approach, we will try to maintain a window of size of K. We will greedily open a window of size K and shrink it until we find an airport. If we did not found any airport, that means the destination is unreachable. We will continue opening the windows from the last stop until we reach the destination.
Algorithm:
- If no airport at destination i.e, airports[x] is 0 return -1.
- Initialize a variable stops with a value of 0.
- Initialize a variable i with value 0.
- Iterate while i is less than (n - k)
- Set j as (i + k)
- While j is greater than i and airports[j] equals 0, decrement j by 1.
- If j is equal to i, return -1.
- If j is equal to x, break.
- Increment stops by 1.
- Set i as j.
- Finally, return stops.