Last Updated: 18 Nov, 2020
Circular Array Loop
Hard
Asked in companies
You are given a circular array 'ARR' of size 'N', consisting of positive and negative integers. For each index 'i', if ARR[i] is positive then move ARR[i] steps in clockwise direction else move ARR[i] steps in counterclockwise direction.
Assume that the first ( ARR[0] ) and last element ( ARR[N - 1] ) are adjacent to each other i.e. when we move in the counterclockwise direction, the next element for ARR[0] is ARR[N - 1] and similarly, when we move in the clockwise direction, the next element for ARR[N - 1] is ARR[0].
Determine if there is a cycle present in the array or not. A cycle must hold the following conditions:
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.
Input Format :
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.
Output Format :
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.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
-10^5 <= ARR[i] <= 10^5 (ARR[i] != 0)
Time Limit: 1 sec
Approaches
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.