Task
Given an array of non-negative integers a
, determine the minimum number of rightward jumps required to jump "outside" the array, starting at position 0, or return zero/null if it is not possible to do so.
A jump from index i
is defined to be an increase in array index by at most a[i]
.
A jump outside is a jump where the index resulting from the jump i
is out-of-bounds for the array, so for 1-based indexing i>length(a)
, and for 0-based indexing, i>=length(a)
.
Example 1
Consider Array = [4,0,2,0,2,0]
:
Array[0] = 4 -> You can jump 4 field
Array[1] = 0 -> You can jump 0 field
Array[2] = 2 -> You can jump 2 field
Array[3] = 0 -> You can jump 0 field
Array[4] = 2 -> You can jump 2 field
Array[5] = 0 -> You can jump 0 field
The shortest path by "jumping" to go out-of-bounds has length 2
:
We could jump from 0->2->4->outside
which has length 3
but 0->4->outside
has length 2
so we return 2
.
Example 2
Suppose Array=[0,1,2,3,2,1]
:
Array[0] = 0 -> You can jump 0 fields
Array[1] = 1 -> You can jump 1 field
Array[2] = 2 -> You can jump 2 field
Array[3] = 3 -> You can jump 3 field
Array[4] = 2 -> You can jump 2 field
Array[5] = 1 -> You can jump 1 field
In this case, it is impossible to jump outside the array, so we should return a zero/null or any non deterministic value like ∞
.
Example 3
Suppose Array=[4]
:
Array[0] = 4 -> You can jump 4 field
We can directly jump from index 0 outside of the array, with just one jump, so we return 1
.
Edit:
Due to multiple questions about the return value:
Returning ∞
is totally valid, if there is no chance to escape.
Because, if there is a chance, we can define that number.
This is code-golf, so the shortest code in bytes wins!
[2, 3, 1, 1]
. \$\endgroup\$