Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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:

Check for loop 1

Our first element at index 0 is 1

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

Check for loop 2

We moved from index 0 => 1

In the next step,

Check for loop 3

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, 

Check for loop 4

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

Check for loop 5

We moved from index 0 => 1

In the next step,

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

Check for loop 6

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

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")

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

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 Seriesproblems listsproblems, participate in contests, and take a look at our courses that will help you become proficient in DSA in PythonC++Java, and Competitive programmingThese Interview experiences will give you a heads-up on what you must prepare for!

Thank you!

Previous article
Advantages and Disadvantages of Array
Next article
How to take array input from user in java?
Live masterclass