Last Updated: 5 Dec, 2021
Last Exam
Moderate
Asked in company
The Ninja had finished his last exam and wanted to reach home as soon as possible to play video games. His exam centre lies at position 0, and his home is at position ‘X’ on the x-axis. The ninja jumps according to the following rules:
- He can jump exactly ‘A’ positions to the right.
- He can jump exactly ‘B’ positions to the left.
- He cannot jump to the left twice in a row.
- He cannot jump to any restricted positions.
- He can jump beyond his home but cannot jump to positions with negative integers.
You are given an array ‘RESTRICTED’ containing the restricted positions. You are also given three integers, ‘A’, ‘B’, and ‘X’. Your task is to find the minimum number of jumps needed for the ninja to reach his home. If there is no possible sequence of jumps that lands ninja on position ‘X’. return -1.
For Example:
You are given ‘RESTRICTED’ = {1, 3}, ‘A’ = 2, ‘B’ = 1 and ‘X’ = 4. Then ninjas requires two jumps(0 -> 2 -> 4) to reach his home.
Input Format :
The first line of the input contains a single integer 'T', representing the number of test cases.
The first line of each test case contains four space-separated integers, ‘A’, ‘B’, ‘X’, and ‘N’.
The Second line contains ‘N’ space-separated integers representing the restricted positions.
Output Format:
For each test case, print the minimum number of jumps needed for the ninja to reach his home.
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 1000
1 <= A, B, RESTRICTED[i] <= 2000
0 <= X <= 2000
RESTRICTED contains distinct elements.
Position X is not restricted.
Time Limit: 1 sec
Approaches
Prerequisite: Breadth-First Search
In this approach, we perform Breadth-First Search from position 0.
For each position:
- If the current position is the target position, we return the number of moves.
- Otherwise, if the current position is already visited, check the next position stored in the BFS queue.
- Otherwise, we will make a jump to the next position. We have two choices for the next position:
- The right jump to (Position + A) if (Position + A) is not restricted and less than the max jump.
- The left jump to (Position - B) if (Position - B) is not restricted and greater than 0, and the previous jump was a right jump.
We will add the next possible position to the BFS queue.
At each jump, we will increment the number of the moves.
The max jump is ((maximum value of ‘RESTRICTED’) + 2 * ‘B’). If we don’t set the max jump, we will keep on adding ‘A’ to the current position and jumping forward to infinity.
Algorithm :
- Initialize a set ‘RESTRICTEDSET’ to store restricted positions.
- Set ‘MAXJUMP’ to 2000 + 2 * b as the maximum value RESTRICTED[i] can be 2000 according to the constraints.
- Iterate ‘NUM’ in ‘RESTRICTED’:
- Add ‘NUM’ to ‘RESTRICTEDSET’.
- Set ‘MAXJUMP’ as the maximum (‘NUM’ + 2 * b) and ‘MAXJUMP’.
- Initialize a queue ‘QUEUE’ of pairs. Each pair has two fields, an integer value to store positions and a boolean value which is true if we arrived at this position by making a left jump otherwise false.
- Add [0, false] to ‘QUEUE’.
- Initialize a set ‘VISITED’ to store already visited positions.
- Set ‘MOVES’ to 0.
- Iterate while ‘QUEUE’ is not empty:
- Set ‘SIZE’ as ‘QUEUE.SIZE’.
- Iterate ‘I’ in 0 to ‘SIZE’:
- Get the current pair from the queue. Set ‘PAIR’ as ‘QUEUE.POLL’.
- Get the current position. Set ‘POS’ as ‘PAIR.KEY’.
- If ‘POS’ is equal to ‘X’, return moves.
- If ‘POS’ is present in ‘VISITED’, continue.
- Add ‘POS’ to ‘VISITED’.
- Set ‘LEFT’ as ‘POS’ - ‘B’.
- Set ‘RIGHT’ as ‘POS’ + ‘A’.
- If ‘PAIR.VALUE’ is ‘FALSE’ and the position ‘LEFT’ is not restricted, add [‘LEFT’, true] to ‘QUEUE’.
- If the position ‘RIGHT’ is not restricted and less than max jump, add [‘RIGHT’, false] to ‘QUEUE’.
- Increment ‘MOVES’ by 1.
- If we never reached home, return -1.
Prerequisite: Depth-FIrst Search
The basic idea of this approach is similar to approach 1. In this approach, we perform Depth-First Search from position 0.
For each position:
- If the current position is the target position, we return the number of moves.
- Otherwise, we will make a jump to the next position. We have two choices for the next position:
- The right jump to (Position + A) if (Position + A) is not visited and less than the max jump.
- The left jump to (Position - B) if (Position - B) is not visited, and greater than 0, and the previous jump was a right jump.
We will Call DFS on the next possible position.
We will increase the jumps field by one at each DFS call.
We will add all the restricted positions to the visited set so that we don’t visit restricted positions in DFS traversal.
The max jump is ((maximum value of ‘RESTRICTED’) + 2 * ‘B’). If we don’t set the max jump, we will keep on adding ‘A’ to the current position and jumping forward to infinity.
Algorithm :
- Initialize a set ‘VSITED’ to store visited positions.
- All the restricted positions to the visited set.
- Set ‘MINJUMPS’ as maximum integer value ‘MAXJUMPS’ as 2000 + 2 * b.
- Add 0 to ‘VISITED’.
- Call DFS on position 0.
- If ‘MINJUMPS’ is unchanged from the initial value, return -1. Otherwise, return ‘MINJUMPS’.
Maintain a function ‘DFS’(int ‘POS’, int ‘JUMPS’, string ‘PREVIOUSJJUMP’, int ‘X’, int ‘A’, int ‘B’)
- Base case. If ‘POS’ is equal to ‘X’.
- Set ‘MINJUMPS’ to the minimum of ‘JUMPS’ and ‘MINJUMPS’.
- Return.
- If the previous jump was to the right, add ‘POS’ to ‘VISITED’.
- Set ‘LEFT’ as ‘POS’ - ‘B’.
- Set ‘RIGHT’ as ‘POS’ + ‘A’.
- If 'RIGHT' is not visited and less than max jump, call DFS on ‘RIGHT’.
- If 'LEFT' is not visited and the previous jump was not to the left and less than max jump, call DFS on ‘LEFT’.
- Return.