1.
Introduction
2.
What is Loop in Array?
2.1.
Example 1
2.2.
Example 2
3.
Algorithm
4.
Implementation
4.1.
C++
4.1.1.
Output
4.2.
Python
4.2.1.
Output
4.3.
Java
4.3.1.
Output
5.
5.1.
What is an array?
5.2.
What are the operations that can be performed on an array?
5.3.
What are the types of arrays?
5.4.
What are the applications of arrays?
5.5.
Are arrays homogeneous?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Check loop in array according to given constraints

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## Introduction

An array is a type of data structure 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. Let's see how to check loop in Array according to given constraints

How do we check loop in array according to given constraints?

Let us say we have an array arr[0..n-1] consisting of both positive and negative elements. We need to find if there is a cycle or loop in the array with provided rules of movements.

If the element at index i is positive, then we move arr[i]%n steps forward. In other words, next index to visit is (i + arr[i])%n.  Contrarily, If the element is negative, then we move arr[i]%n steps backward, and the next index to visit would be (i â€“ arr[i])%n.If the value of arr[i]%n is zero, then there shall be no movement from index i. Number of elements is represented by n.

Must Read, Array Implementation of Queue and Rabin Karp Algorithm

## What is Loop in Array?

Let's see a few examples to understand our problem to check loop in array according to given constraints.

### Example 1

Input:

``arr[] = {1, 2, -1, 2, 3 }``

Output:

``Loop found``

Explanation:

Our first element at index 0 is 1

It is positive, so we'll be moving arr[i] % n steps forward

We moved from index 0 => 1

In the next step,

arr[1] = 2 is positive so weâ€™ll move from element 2 at index 1 to element 2 at index 3

index 0 => 1=> 3

In the next step,

arr[3] = 2 is positive, so we'll move from element 2 at index 3 to element 1 at index 0, forming a loop.

index 0 => 1=> 3 => 0

Hence we can conclude that we check loop in array according to given constraints and the above array forms a loop according to the given constraints.

### Example 2

Input:

``arr[] = {1, 2}``

Output:

``Loop not found``

Explanation:

Our first element at index 0 is 1

It is positive, so we'll be moving arr[i] % n steps forward

We moved from index 0 => 1

In the next step,

arr[1] = 2 is positive but 2%2 = 0 so there is no movement

Hence we can conclude that we check loop in array according to given constraints and the above array doesn't form a loop.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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

• Print loop found

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

vector<bool> &visit, vector<bool> &recurr)
{
visit[v] = true;
recurr[v] = true;
{
{
return true;
}

// There is a cycle if adjacent is visited
else if (visit[adj[v][i]] == true &&
return true;
}

recurr[v] = false;
return false;
}

// Returns true if arr[] has cycle
bool isCycle(int arr[], int n)
{
for (int i=0; i<n; i++)
if (i != (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)
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;
}``````

#### Output

``Yes loop found``

### Python

``````# Python program to check for loop in an array

visit[v] = True
recurr[v] = True
visit, recurr)):
return True

# There is a cycle if adjacent is visited
else if (visit[adj[v][i]] == True and
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):

# DFS traversal of the graph to detect cycle
visited = [False] * n
recur = [False] * n
for i in range(n):
if (visited[i] == False):
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")

``````

#### 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++)
{
{
return true;
}

else if (visit.elemenstAt(adj[v].elementsAt(i)) == true &&
return true;
}
recurr.set(v, false);
return false;
}

static boolean isCycle(int[] arr, int n)
{

for (int i = 0; i < n; i++)
if (i != (i + arr[i] + n) % n &&

// DFS traversal of graph to detect cycle
Vector<Boolean> visited = new Vector<>();
for (int i = 0; i < n; i++)
Vector<Boolean> recur = new Vector<>();
for (int i = 0; i < n; i++)

for (int i = 0; i < n; i++)
if (visit.elementsAt(i) == false)
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");
}
}

``````

#### Output

``Yes loop found``

Also see, Morris Traversal for Inorder.

Must Read What are Loops in Java.

### 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