Problem Explanation
In this problem we are given an array denoting the number of steps the pawn can take. We have to output the maximum number of steps the pawn can take to reach the end, or output -1 if it is impossible.
Approach
You are required to reach the goal which is the last element in the array using the maximum steps. So we can start from the second last element and iterate to the start of the array and check for element if we can reach the goal. If we can we take take step since we have to take the maximum amount of steps and update the goal.
Algorithm
- We maintain a goal variable which is initialized as n-1 and an ans variable initialized as 1.
- we iterate from the second last element of the array to the first element and check if we can reach the goal from each element.
- If we can reach the goal from a element the goal is changed to that element and the ans is incremented by 1.
- At the end we check if the goal is the index of the first element i.e. 0 or not.
- If it is 0 we can reach the end and we output the ans.
- Otherwise, we output -1.