Given an array of positive integers, you are at index 0, each element will represents maximum jump length. Check if you can reach to last index.
Example 1: Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
The solution is very simple.
We take a variable “step” and initialize with array[0]. Then we move to the next element, then “step” will be decremented by one. The “step” will always indicate the remaining moves.
Then starting from array [1], take the maximum value of step and array[i]. At a certain point of time if “step == 0” and is not the end of the array, then return false as it cannot reach the end of the array.
If there is still “steps” left even after reaching the end of the array, then we return “true” as we have already reached the end of the array.
Coming to our example:
array = [2,3,1,1,4] Inital step = 2 Pass 1: step = 2 we passed 1 element, hence decrement step by 1 max of (1, 3) step = 3
Pass 2: step = 3 we passed 1 element, hence decrement step by 1 max of (2, 1) step = 2
Pass 3: step = 2 we passed 1 element, hence decrement step by 1 max of (1, 1) step = 1
Pass 4: step = 1 we passed 1 element, hence decrement step by 1 max of (0, 4) step = 4 We have reached end of the array, hence the result is true.
The solution in C++:
#include<iostream> using namespace std; bool ckeck_can_jump (int array[], int length) { int step = array[0]; for (int i = 1; i < length; i++) { if (step == 0) { return false; } step = max(--step, array[i]); } return true; } int main() { int array[] = {2,3,1,1,4}; //int array[] = {3,2,1,0,4}; int length = 5; bool result = ckeck_can_jump(array, length); if(result) { cout<<"True, we can reach till the end of the array"<<endl; } else { cout<<"False, we cannot reach till the end of the array"<<endl; } }
Output:
True, we can reach till the end of the array
No Responses