Skip to main content

How do I find efficiently, the number of jumps it will take for an element to jump out of an array?

I am trying to write an efficient algorithm that will find the number of jumps it will take for a pawn to exit an array. Lets say we are given an array, for each element in the array if array[k] = n then array[k] is equal to array[k + n];

For example, we have this array [2,3,-1,1,3].

Initially the pawn is at array[0], on first jump it moves from array[0] to array[2] because 0 + array[0] is equal to 2. on the second jump, the pawn moves from A[2] to A[1] because 2 + A[2] = 1; on the third jump, the pawn moves from A[1] to A[4] because 1 + A[1] = 4; on the fourth jump, the pawn jumps out of the array. It returns 4 for this test case.

If the pawn cant jump out of the array we return -1;

Below is the algorithm I wrote for this problem and it works for a few test cases but fails large test cases. How can I make this algorithm more efficient.

function jumpOut(A) { 
  let start = 0;
  let end = A.length - 1
  let pawn = 0;
  
  while (start < end){
    pawn= start + A[start]  
    start++;
  }
  
  if(pawn === end){
    return pawn
  }
  
  return -1;
} 

Via Active questions tagged javascript - Stack Overflow https://ift.tt/LOBHu5m

Comments