Given an array of Integers arr,
from an element val = arr[i], you can go to element i to i+val.
If val is zero, you cannot move forward.
find the least selection to reach end of the array.
example: 1 3 5 8 9 2 6 7 6 8 9
@index 0, can go to 1
@index 1, can go to 4.
if index 3 and 4 choosen, it will reach to end frm there only.
Give an algorithm and program.
This can be solved with greedy aproach.
Assume we are at index i,
So For all i ..to i+a[i] index check for the max value value
of k+a[k], where i
We can prove the correctness of this .
If k+a[k] having maximum value then any value except the k in range of i to i+a[i]
will be less than range reachable by k.
So by choosing k, you still can choose the option available with other indexs.
from an element val = arr[i], you can go to element i to i+val.
If val is zero, you cannot move forward.
find the least selection to reach end of the array.
example: 1 3 5 8 9 2 6 7 6 8 9
@index 0, can go to 1
@index 1, can go to 4.
if index 3 and 4 choosen, it will reach to end frm there only.
Give an algorithm and program.
This can be solved with greedy aproach.
Assume we are at index i,
So For all i ..to i+a[i] index check for the max value value
of k+a[k], where i
We can prove the correctness of this .
If k+a[k] having maximum value then any value except the k in range of i to i+a[i]
will be less than range reachable by k.
So by choosing k, you still can choose the option available with other indexs.
Comments
Post a Comment