Minimum Jumps To Reach End

Minimum Jumps To Reach End

Hard Python Loops 19 views
Explanation Complexity

Problem Statement

For each testcase you get array where a[i] is max jump length from i. Compute minimum jumps to reach last index, else -1.

Input Format

First integer t. For each: n then n integers.

Output Format

t lines min jumps.

Example

2
5
2 3 1 1 4
5
3 2 1 0 4
2
-1

Constraints

Sum of n over all testcases

Input / Output Format

Input Format
First integer t. For each: n then n integers.
Output Format
t lines min jumps.
Constraints
Sum of n over all testcases

Examples

Input:
2 5 2 3 1 1 4 5 3 2 1 0 4
Output:
2 -1

Example Solution (Public)

Python 
import sys
p=sys.stdin.read().strip().split()
if not p:
  sys.exit(0)
it=iter(p)
t=int(next(it))
out=[]
for _ in range(t):
  n=int(next(it))
  a=[int(next(it)) for _ in range(n)]
  if n<=1:
    out.append('0')
    continue
  if a[0]==0:
    out.append('-1')
    continue
  jumps=1
  maxReach=a[0]
  step=a[0]
  ok=True
  for i in range(1,n):
    if i==n-1:
      break
    if i+a[i]>maxReach:
      maxReach=i+a[i]
    step-=1
    if step==0:
      jumps+=1
      if i>=maxReach:
        ok=False
        break
      step=maxReach-i
  out.append(str(jumps if ok else -1))
sys.stdout.write('\
'.join(out))

Official Solution Code

import sys
p=sys.stdin.read().strip().split()
if not p:
  sys.exit(0)
it=iter(p)
t=int(next(it))
out=[]
for _ in range(t):
  n=int(next(it))
  a=[int(next(it)) for _ in range(n)]
  if n<=1:
    out.append('0')
    continue
  if a[0]==0:
    out.append('-1')
    continue
  jumps=1
  maxReach=a[0]
  step=a[0]
  ok=True
  for i in range(1,n):
    if i==n-1:
      break
    if i+a[i]>maxReach:
      maxReach=i+a[i]
    step-=1
    if step==0:
      jumps+=1
      if i>=maxReach:
        ok=False
        break
      step=maxReach-i
  out.append(str(jumps if ok else -1))
sys.stdout.write('\
'.join(out))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.