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.

MBo · Accepted Answer · 2022-11-24 06:12:14Z

3

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;
}

edited Nov 24, 2022 at 6:12

answered Nov 24, 2022 at 6:07

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Could you help me with this Array Problem?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related