Explanation:
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the 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.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach 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 certain point of time if “step == 0” and is not the end of the array, then return false as it cannot reach 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 end of the array.
Coming to our example:
Solution in C++
/*
* File : jump_game.cpp
* Author : ajay.thousand@gmail.com
* Copyright: @ prodevelopertutorial.com
*/
#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;
}
}