Help Ninja to Cross River

Hard
0/120
Average time to solve is 20m
profile
Contributed by
10 upvotes
Asked in companies
FacebookAppleThought Works

Problem statement

Ninja is standing on the edge of a river and wants to cross the river. There is a wooden bridge over the river but some units of the bridge are damaged. Ninja can not step over a damaged unit of the bridge. All the safe units of the bridge are in an array/list ‘SAFE’ which is sorted in increasing order.

Ninja is currently standing on the first safe unit of the bridge and has to reach the last safe unit of the bridge by jumping.

There are some restrictions on the size of jump Ninja can make:

1. The first jump will always be of 1 unit.
2. If Ninja's previous jump was ‘X’ units, his current jump must be either ‘X’ - 1, ‘X’, or ‘X’ + 1 units.

As Ninja is warming up before crossing the bridge, he asks you for help. You need to find out whether Ninja can cross the river or not and return TRUE if Ninja can cross the river else return FALSE.

For example :

If ‘SAFE’ = [1, 2, 4, 7] then it can shown in below image where :
Red cell means that the unit is damaged.
Green cell means that the unit is safe.
We can see Ninja can reach the last unit by making jumps of size 1 , 2 and 3.

Example

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains a single integer ‘N’ denoting the size of ‘SAFE’ or we can say the number of safe units.

The second line contains ‘N’ space-separated distinct integers denoting the elements of ‘SAFE’.

Output format:

For each test case return, true if Ninja can cross the river else return false.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints

1 <= T <=10
2 <= N <= 10^3
0 <= SAFE[i] <= 10^5

Time limit: 1 sec

Sample input 1:

2
5
0 1 3 5 7
2
1 3

Sample output 1:

YES
NO

Explanation for sample input 1:

For test case 1:
1. The first jump will be of 1 unit and Ninja will reach the 2nd unit.
2. The second jump will be of 2 (‘X’+1) units and Ninja will reach the 3rd unit.
3. The third jump will be of 2 (‘X’) units and Ninja will reach the 4th unit.
4. The fourth jump will be of 2 (‘X’) units and Ninja will reach the last unit.

For test case 2:
There are only two safe units and Ninja can make a jump of only 1 unit in the first turn so Ninja can not reach the last unit.

Sample input 2:

2
2
2 3
6
2 3 4 6 7 10

Sample output 2:

YES
NO

Explanation for sample input 2:

For test case 1:
There are only two safe units and Ninja can make a jump of only 1 unit in the first turn so Ninja will reach the last unit.

For test case 2:
There is no possible sequence of jumps that can lead the Ninja to the last safe unit.
Hint

 Can you think about a recursive solution.?

Approaches (3)
Recursion

Complete Algorithm:

  • First of all, we will make a HashMap say ‘MY_MAP’ to store safe units where the key will be ‘SAFE[i]’ and the value will be ‘i’.
  • We will make a helper recursive function named ‘SOLVE’ which will receive 4 parameters ‘SAFE’, ‘MY_MAP’, index of current unit ‘INDEX’ and size of previous jump ‘X’.
  • Base Case:
    • If ‘INDEX’ is equal to last safe unit:
      • Return true.
  • Recursive Calls:
    • Now we have three possible places to go :
      • ‘POS1’ = ‘SAFE[INDEX]’ + ’X’.
      • ‘POS2’ = ‘SAFE[INDEX]’ + ‘X’ - 1.
      • ‘POS3’ = ‘SAFE[INDEX]’ + ‘X’ +1.
    • If “POS1’ exists in ‘MY_MAP’ then do:
      • Make a recursive call with ‘INDEX’ as ‘MY_MAP[POS1]’ and keep ‘X’ the same.
    • Similarly, we will check for ‘POS2’ and ‘POS3’.
    • If the recursive call returns true for any of these three we will return true. The idea is very simple, as standing on any safe unit Ninja will always have a maximum of three choices so we will use recursion to search for all possible options.
  • Return the value returned by SOLVE().
Time Complexity

O(3 ^ N), where ‘N’ is the size of array/list ‘SAFE’.

 

As during each call to function we are making further 3 calls thus making time complexity as O(3 ^ N).

Space Complexity

O(3 ^ N), where ‘N’ is the size of array/list ‘SAFE’.

 

This is the space used by the recursion stack to store 3 ^ N calls.

Code Solution
(100% EXP penalty)
Help Ninja to Cross River
Full screen
Console