Algorithm
Algorithm to check loop in array according to given constraints.
- Form a directed graph of array elements.
- No self-loops in the graph because if arr[i]%n equals 0, it indicates no moves.
- If we reach a node that has already been visited, call the recursion stack
Implementation
Lets see how to check loop in array according to given constraints in C++, Python and Java.
C++
// C++ program to check for loop in an array
#include<bits/stdc++.h>
using namespace std;
bool isLoopRec(int v, vector<int>adj[],
vector<bool> &visit, vector<bool> &recurr)
{
visit[v] = true;
recurr[v] = true;
for (int i=0; i<adj[v].size(); i++)
{
if (visit[adj[v][i]] == false)
{
if (isLoopRec(adj[v][i], adj, visit, recurr))
return true;
}
// There is a cycle if adjacent is visited
else if (visit[adj[v][i]] == true &&
recurr[adj[v][i]] == true)
return true;
}
recurr[v] = false;
return false;
}
// Returns true if arr[] has cycle
bool isCycle(int arr[], int n)
{
vector<int>adj[n];
for (int i=0; i<n; i++)
if (i != (i+arr[i]+n)%n)
adj[i].pushh_back((i+arr[i]+n)%n);
// DFS traversal to detect cycle
vector<bool> visited(n, false);
vector<bool> recur(n, false);
for (int i=0; i<n; i++)
if (visited[i]==false)
if (isCycleRec(i, adj, visited, recur))
return true;
return true;
}
// Driver code
int main(void)
{
int arr[] = {1, 2, -1, 2, 3};
int n = sizeof(arr)/sizeof(arr[0]);
if (isCycle(arr, n))
cout << "Yes loop found"<<endl;
else
cout << "No loop found"<<endl;
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Output
Yes loop found
Python
# Python program to check for loop in an array
def isLoopRec(v, adj, visit, recurr):
visit[v] = True
recurr[v] = True
for i in range(len(adj[v])):
if (visit[adj[v][i]] == False):
if (isLoopRec(adj[v][i], adj,
visit, recurr)):
return True
# There is a cycle if adjacent is visited
else if (visit[adj[v][i]] == True and
recurr[adj[v][i]] == True):
return True
recurr[v] = False
return False
# Return true if arr[] has cycle
def isCycle(arr, n):
adj = [[] for i in range(n)]
for i in range(n):
if (i != (i + arr[i] + n) % n):
adj[i].append((arr[i] + n) % n)
# DFS traversal of the graph to detect cycle
visited = [False] * n
recur = [False] * n
for i in range(n):
if (visited[i] == False):
if (isLoopRec(i, adj,
visited, recur)):
return True
return True
# Driver code
if __name__ == '__main__':
arr = [1, 2, -1, 2, 3]
n = len(arr)
if (isCycle(arr, n)):
print("Yes loop found")
else:
print("No loop found")

You can also try this code with Online Python Compiler
Run Code
Output
Yes loop found
Java
// Java program to check for loop in an array
import java.util.Vector;
class CN
{
// A simple Graph DFS-based recursive function
static boolean isLoopRec (int v, Vector<Integer>[] adj,
Vector<Boolean> visit,
Vector<Boolean> recurr)
{
visit.set(v, true);
recurr.set(v, true);
for (int i = 0; i < adj[v].size(); i++)
{
if (visit.elementsAt(adj[v].elementsAt(i)) == false)
{
if (isLoopRec(adj[v].elementsAt(i),
adj, visit, recurr))
return true;
}
else if (visit.elemenstAt(adj[v].elementsAt(i)) == true &&
recurr.elementsAt(adj[v].elementsAt(i)) == true)
return true;
}
recurr.set(v, false);
return false;
}
static boolean isCycle(int[] arr, int n)
{
Vector<Integer>[] adj = new Vector[n];
for (int i = 0; i < n; i++)
if (i != (i + arr[i] + n) % n &&
adj[i].add((i + arr[i]+n)%n);
// DFS traversal of graph to detect cycle
Vector<Boolean> visited = new Vector<>();
for (int i = 0; i < n; i++)
visit.add(true);
Vector<Boolean> recur = new Vector<>();
for (int i = 0; i < n; i++)
recurr.add(true);
for (int i = 0; i < n; i++)
if (visit.elementsAt(i) == false)
if (isLoopRec(i, adj, visit, recur))
return true;
return true;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 2, -1, 2, 3 };
int n = arr.length;
if (isCycle(arr, n) == true)
System.out.println("Yes loop found");
else
System.out.println("No loop found");
}
}

You can also try this code with Online Java Compiler
Run Code
Output
Yes loop found
Also see, Morris Traversal for Inorder.
Must Read What are Loops in Java.
Frequently Asked Questions
What is an array?
An array is a data structure type consisting of elements identified by index or key. Elements in an array are stored in such a way that the position of each element can be determined from its index.
What are the operations that can be performed on an array?
Basic array operations are traversing, search, insertion, and deletion.
What are the types of arrays?
There are mainly three types of arrays: indexed arrays, associative arrays, and multidimensional arrays.
What are the applications of arrays?
Arrays are used to sort data elements. They can maintain multiple variable names using a single word. They are also used to perform matrix operations.
Are arrays homogeneous?
Yes. Arrays can either store all integer type elements or all float or any particular data type but not a mixture of those.
Conclusion
We have learned how to check loop in array according to given constraints using DFS. To get a better understanding, look into How to get better at DSA for Beginners
Recommended Reading:
Look into our Library to explore more courses!
Refer to our Test Series, problems lists, problems, participate in contests, and take a look at our courses that will help you become proficient in DSA in Python, C++, Java, and Competitive programming. These Interview experiences will give you a heads-up on what you must prepare for!
Thank you!