Minimum Jumps
Python
Hard
4 views
Problem Description
Read n integers where a[i] is max jump length from i. Output minimum jumps from 0 to n-1 or -1 if not possible.
Input Format
First line n. Second line n integers.
Output Format
One integer minJumps.
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
a=list(map(int,p[1:1+n]))
if n<=1:
sys.stdout.write('0')
else:
if a[0]==0:
sys.stdout.write('-1')
else:
jumps=0
curEnd=0
far=0
ok=True
for i in range(n-1):
if i>far:
ok=False
break
if i+a[i]>far:
far=i+a[i]
if i==curEnd:
jumps+=1
curEnd=far
if curEnd>=n-1:
break
sys.stdout.write(str(jumps if ok and far>=n-1 else -1))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!