There are n stepping stones in a row, numbered 0 to n-1. Stone i has a maximum leap distance a_i, meaning that from stone i you may jump directly to any stone i+1, i+2, ..., i+a_i (never past the last stone). Starting on stone 0, find the minimum number of leaps needed to reach stone n-1. If it cannot be reached, print -1.
Line 1: an integer n.
Line 2: n space-separated non-negative integers a_0 ... a_{n-1}.
A single integer: the minimum number of leaps to reach stone n-1 from stone 0, or -1 if it is impossible. (If n <= 1, you are already there, so the answer is 0.)
Example 1
Input
5 2 3 1 1 4
Expected
2
Explanation
Leap from stone 0 to stone 1 (reach 2), then from stone 1 to stone 4, the last stone (reach 4): 2 leaps total.
Example 2
Input
4 1 0 0 0
Expected
-1
Explanation
From stone 0 you can only reach stone 1, which has a leap distance of 0, so you are stuck there: -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →