Could you help me with this Array Problem?

Question

An array A with N integers . Each element can be treated as a pointer to others : if A[K] = M then A[K] points to A[K+M]. The array defines a sequence of jumps as follows:

• initially, located at element A[0];
• on each jump , moves from current element to the destination pointed to by the current ; i.e. if on element A[K] then it jumps to the element pointed to by A[K];
• it may jump forever or may jump out of the array.

Write a function: that, given a array A with N integers, returns the number of jumps after which it will be out of the array.

Answer 1

Your approach is right, but instant list reallocation can make program slower.

It is claimed that value range is limited, so you can just put off-range constant (like 2000000) into visited cells as sentinel and stop when you meet such value.

Something like this (not checked):

int sol(int[] A) {
    int jump = 0;
    int index = 0;
    int old = 0;
    int alen = A.length;
    while (index < alen && index >= 0) {
        old = index;
        index = A[index] + index;
        if (A[index] >= 2000000)  {
            return -1;
        }
        A[old] = 2000000;
        jump++;
    }
    return jump;
}