CareerCup

Could you please clarify question.

Every element of this array have "next" element to go (including itself). So we can do "next" starting from any element infinite times and always can continue. Thus EVERY possible array will have loop because array is finite. Loop length could be from 0 to N (whole array).

What case could be considered as no-loop array?

It's still not clear for me :)

Need more test cases:

[1, 1, 1, 1, 1, 1, 1] loop? For me it's a full array loop.
[1, 1, 1, 1, 1, 1, 0] loop? For me it's a zero length/self loop on the last element.
[1, 1, 1, 0, 1, 1, 1] loop? Same as previous. But some elements can't be reached from first.
[1, 1, 1, 1, 1, 1, -2, 1, 1] loop? A loop of length three.
[10] loop? A full array self loop :)
[] loop?

From math point of view (theory of permutations) all examples have loops. From 0 to N length. Except last. It's degenerate/edge case.

Is it clear why i'm so confused? :)

Conceptually this problem on finding a loop in a single linked list. Usually people solve such problem by reversing links, or by using two iterators (with step size 1 and 2 consequently).

Save path in map (or int array[65535]) and check index for visiting

This should be similar to link list loop finding problem

If I understood @sergey 's comment above; every finite array has loop in it.
If there are N elements in array then only at the max (N-1) times you can go to distinct position.

At (N-1)th hop you have already visited all the indexes. Hence when you take Nth hop, you will land on one of the reviosuly visited place. Thus it is a loop.

@Sergey, sorry, I should've clarified this. A loop is something that starts and ends at a particular index. In the example, the loop went from 0->2, 2->3, and 3->0, so the loop started and ended with 0. If we have an array of [-1, 2], then this would not be a loop because index 0->1, but 1->1, so we don't start and end with the same index.

static boolean cyclesThroughStart(int start, int... arr) {
		int slowIdx = start;
		int fastIdx = start;
		do {
			slowIdx = f(arr,slowIdx);
			fastIdx = f(arr,f(arr,fastIdx));
			if (slowIdx == start || fastIdx == start) {
				return true;
			}
		} while(slowIdx != fastIdx);
		return false;
	}
	
	static int f(int[] arr,int idx) {
		idx += arr[idx];
		return Math.abs(idx % arr.length);
	}

So, if I read it correctly we are checking whether the cycle passes through the start index.
In which case this code should work:

static boolean cyclesThroughStart(int start, int... arr) {
		int slowIdx = start;
		int fastIdx = start;
		do {
			slowIdx = f(arr,slowIdx);
			fastIdx = f(arr,f(arr,fastIdx));
			if (slowIdx == start || fastIdx == start) {
				return true;
			}
		} while(slowIdx != fastIdx);
		return false;
	}
	
	static int f(int[] arr,int idx) {
		idx += arr[idx];
		return Math.abs(idx % arr.length);
	}

Through dfs

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
bool detect(int v,vector<int>V[],bool visited[],bool recur[],bool& det)
{
visited[v]=true;
recur[v]=true;
for(int i=0;i<V[v].size();i++)
if(visited[V[v][i]]==false)
detect(V[v][i],V,visited,recur,det);
else if(visited[V[v][i]]==true && recur[V[v][i]]==true)
det=true;
recur[v]=false;
}

int main(void)
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
vector<int>V[n+5];
for(int i=0;i<n;i++)
V[i].push_back((i+arr[i]+n)%n);
bool visited[n];
bool recur[n];
memset(visited,0,sizeof(visited));
memset(recur,0,sizeof(recur));
bool x=false;
for(int i=0;i<n;i++)
if(visited[i]==false)
detect(i,V,visited,recur,x);
if(x==false)
cout<<"NO LOOP"<<endl;
else
cout<<"Loop exist"<<endl;
return 0;
}

This is my solution using ArrayList. Suggestions are welcomed.

I am adding every visited index in the arrayList and checking that whether it's been previously added or not. If it is already in the arrayList then there exist a cycle otherwise no cycle.

Even if the array is like [2,0,0,0,0]. There is a cycle after first iteration. Because after reaching at index 2 from the start, in the next iteration I am again visiting it because of the 0 displacement.

If the above situation is not to be taken care of then we can add one more condition to check whether the new value is the same as previous(previous = value at the end of the for loop) value then need to break the loop and return false.

public class FindCycleInArray {

    ArrayList<Integer> arrayList = new ArrayList<Integer>();

    public boolean findCycle(int a[]){
        arrayList.add(0);

        for(int i=0;i<a.length;){
            int value = (i+a[i])% a.length;
           
            if(arrayList.contains(value)){
                return true;
            }
            else{       
                arrayList.add(value);
            }
            i=value;
           
        }

        return false;
    }
}

public static boolean hasLoop(int start, int[] array){
        BitSet db = new BitSet(array.length);
        int pos=start;
        for(int i =0;i<array.length+1;i++){
            if(db.get(pos)) return false;
            db.set(pos);
            pos = pos + array[pos];
            if(pos < 0) pos = (pos%array.length) + array.length-1;
            else  pos = (pos%array.length);
            if (pos == start)  return true;
        }
        return false;
    }

IsLoop() {
return TRUE; // there will always be a loop
}

* 1. Start from first element, if zero then we can't move forward.
* 2. Record the current index in bitset : store.set(i, true);
* 3. If not zero, the nextIndex = (curIndex+a[i])%size
* 4. Move to next index and follow same step.
* 5. If bitset.size() == size , that means we have covered all elements of array.
* 5. If we find bitset.get(index) == true, break the loop and return true;

{{
* 1. Start from first element, if zero then we can't move forward.
* 2. Record the current index in bitset : store.set(i, true);
* 3. If not zero, the nextIndex = (curIndex+a[i])%size
* 4. Move to next index and follow same step.
* 5. If bitset.size() == size , that means we have covered all elements of array.
* 5. If we find bitset.get(index) == true, break the loop and return true;
}}