A climber crosses a quarry along n ledges numbered 0 to n-1, starting on ledge 0. From ledge i the climber can leap forward to any ledge j with i < j <= i + a[i], where a[i] is the maximum forward reach from ledge i (a reach of 0 means no leap is possible from that ledge). The climber only moves forward.
Report the minimum number of leaps needed to reach the last ledge (ledge n-1). If the last ledge cannot be reached, report -1. If the climber already starts on the last ledge, the answer is 0.
Line 1: the integer n.
Line 2: n space-separated non-negative integers a[0] a[1] ... a[n-1].
A single integer: the fewest leaps to reach the last ledge, or -1 if impossible.
Example 1
Input
5 2 3 1 1 4
Expected
2
Explanation
Leap 0 -> 1 (reach 2), then 1 -> 4 (reach 3). Two leaps reach the last ledge, and no single leap can.
Example 2
Input
3 1 0 4
Expected
-1
Explanation
From ledge 0 you can only reach ledge 1, whose reach is 0, so ledge 2 is unreachable: answer -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 →