Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 18 Nov, 2020

Hard

```
1. A cycle must start and end at the same index.
2. The cycle’s length should be greater than 1. For example, if the given array is {1,-2,4,1} then there is a cycle of length 1 from index 3 (1 based indexing).
3. All movements in a cycle must follow a single direction, they should be either in a clockwise or counterclockwise direction.
```

```
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
The first line of each test case contains a positive integer N, which represents the size of the circular array.
The next line contains 'N' single space-separated integers representing the elements of the circular array.
```

```
For each test case, print “True” if there is a cycle, else print “False”.
Print the output of each test case in a separate line.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
1 <= N <= 10^5
-10^5 <= ARR[i] <= 10^5 (ARR[i] != 0)
Time Limit: 1 sec
```

In this approach, for each index, we will check if there can be a cycle passing through this index. We will follow the below steps for every index idx.

Algorithm

- If |Arr[idx]| % N = 0, means there is a cycle of length 1, so we move to the next index.
- Make a boolean array to store the visited indices, initially only idx will be visited.
- Move Arr[idx] steps, i.e, update the idx to (idx + A[idx] + K*N) % N (Here, we are adding a multiple of N to make value non-negative).
- We will do the above steps until we reach a visited index or we reach an index from where we have to move in the opposite direction.
- If we reach a visited index which is the same index from where we started, then there is a cycle.

We will define a state array which will denote the current state of indices.

- state[idx] = 0, idx is unvisited.
- state[idx] = 1, idx is visited, but we are checking if there can be a cycle through this.
- state[idx] = 2, idx is visited, no cycle through index idx.

Initially, all indices are in state 0.

We will make the state equal to 2 for those indices which contain cycle of length 1, means state[idx] = 2 ,if |Arr[idx]| % N = 0.

Iterate over the indices and if it’s state is 0, then we will recursively check if there can be a cycle.

Recursive State: circularArrayLoopHelper(Arr, idx, dir), where Arr is the given array, idx is the current index and dir is the direction in which we are moving (dir = Arr[idx]/abs(Arr[idx]), where abs gives the absolute value).

The recursive function will return true if there is a cycle else false.

- Find the next index, nxtIdx = (Arr[idx] + idx + K*N) % N (Here, we are adding a multiple N to make value non-negative).
- If the next index is in a different direction, then mark the state equal to 2 ( since no cycle can include this index ) and return false.
- If state of nxtIdx is 0, call the recursive function circularArrayLoopHelper(Arr, nxtIdx, dir)
- If the state of nxtIdx is 1, it means a cycle exists and we will return true.

Similar problems

Longest Subarray With Zero Sum

Moderate

Posted: 3 Nov, 2022

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Ninja And The Strictly Increasing Array

Moderate

Posted: 27 Nov, 2022

Negative To The End

Easy

Posted: 16 Dec, 2022

Find Duplicate in Array

Easy

Posted: 5 Jun, 2023