Minimum Stop Required To Reach The Destination

Moderate
0/80
profile
Contributed by
0 upvote
Asked in companies
IntuitJosh Technology GroupNagarro Software

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
6 2 4
1 1 1 0 1 0
4 3 3
1 0 1 1
Sample Output 1:
 1
 0
Explanation:
For the first test case, 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.

For the second test case, the answer will be 0. The plane can directly reach the destination without making any stop. Hence the total number of stops is 0.
Sample Input 2:
2
4 2 3
1 0 0 1
5 3 2
1 0 1 0 0
Sample Output 2:
-1
0
Hint

Find the shortest path to the destination

Approaches (3)
Breadth-First Search

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.
Time Complexity

O(N * K), where N is the size of the input array ‘AIRPORTS’ and ‘K’ is the given integer.
 

Every element of the input array will be added to the ‘Q’ only once’, for every element in the ‘Q’ we will check the next ‘K’ points. Hence the overall time complexity is O(N * K).

Space Complexity

O(N).
 

The size of queue ‘Q’ and boolean array ‘VISITED’ will be at most ‘N’. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Minimum Stop Required To Reach The Destination
Full screen
Console