Last Exam

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
1 upvote
Asked in company
PhonePe

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 1 4 2
1 3 
3 1 3
1 2 7
Sample Output 1:
2
3
Explanation of Sample Input 1:
For the second test case, the ninjas require two jumps(0 -> 2 -> 4) to reach his home.

For the second test case, the ninjas require three jumps(0 -> 3 -> 6 -> 5) to reach his home.
Sample Input 2:
2
2 1 5 1
1
3 2 4
1 2 3 7
Sample Output 2:
4
-1
Hint

Find the shortest path to home.

Approaches (2)
Breadth-First Search

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

O(A + B + MAX(X, MAX(RESTRICTED)), where 'A', 'B', and 'X' are the input integers and 'MAX'('RESTRICTED') is the maximum element of 'RESTRICTED' array.

 

The maximum number of jumps is A + B + MAX(X, MAX(RESTRICTED). Hence, the total time complexity is O(A + B + MAX(X, MAX(RESTRICTED)).

Space Complexity

O(A + B + MAX(X, MAX(RESTRICTED)).
 

We may have to store a maximum of (A + B + MAX(X, MAX(RESTRICTED)) states in BFS queue. Hence, the total space complexity is O(A + B + MAX(X, MAX(RESTRICTED)).

Code Solution
(100% EXP penalty)
Last Exam
Full screen
Console