Circular Array Cycle

Determine whether a circular array of relative indices contains a complete cycle.

** Note: Intentionally vague!

Something things to think about (and ask)

• Can you provide an example?

• What does a complete cycle mean?

• What to the relative indices represent?

• What does a negative index represent?

Specified: We begin at cell ar[0]. Each ar[i] indicates how many positions to forward forward or backward. (e.g., -1 indicates moving to the previous cell, 2 to the second next cell and 0 to the same cell). A complete cycle corresponds to visiting all the cells, only once.

My Approach: I kept an additional memory component that tracks visited positions. I know that in a complete cycle, I would have to at most iterate through the length of the array. Otherwise revisiting the same cell would mean that the sequence will begin to repeat. With negative indices, one thing I can do is continue adding the size of the array until the number is position. This is a slow and iterative process, but the equivalently fastest approach would be see how many times I would have to add in order to make it position, and then just add that. Finally, once a full iteration is through, I iterate through the visited vector to confirm all positions are visited.

Complexity: O(N) time and space

bool has_cycle(vector<int> &ar)
{
    vector<bool> visited(ar.size());
    auto next_index = [&](int index) {
        int target = index + ar[index];
        if (target < 0) {
            int num_times_till_pos = abs(ceil(target / ar.size()));
            target += (num_times_till_pos * ar.size());
        }
        return target % ar.size();
    };

    int iter = next_index(0);
    for (int i = 0; i < ar.size(); i++) {
        if (visited[iter] == true) return false;
        visited[iter] = true;
        iter = next_index(iter);
    }

    for (bool b : visited) {
        if (!b) return false;
    }

    return true;
}

Some Testing

int main()
{
    //                 3 2  1
    vector<int> t1 = { 2,2,-1 };

    //                     2
    //                     1
    vector<int> t2 = { 2,2,0 };

    //                 2
    //                 1
    vector<int> t3 = { 0 };

    //                 2   1
    vector<int> t4 = { 1, -1 };

    //                 3   1  2
    vector<int> t5 = { 1, -2, 1 };

    //                     3
    //                     1     2
    vector<int> t6 = { 1, -6, 7, 2 };

    //                 5  1  4 2  3
    vector<int> t7 = { 1,-3,-2,1,-2 };

    assert(has_cycle(t1) == true);
    assert(has_cycle(t2) == false);
    assert(has_cycle(t3) == true);
    assert(has_cycle(t4) == true);
    assert(has_cycle(t5) == true);
    assert(has_cycle(t6) == false);
    assert(has_cycle(t7) == true);
}