Problem

Submissions

Hints & solutions

Discuss

Circular Array Loop

Hard

0/120

Average time to solve is 45m

Contributed by

3 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

3
5
2 -1 1 2 2
2
-1 2
5
-2 1 -1 -2 -2

Sample Output 1 :

True
False
False

Explanation For Sample Input 1 :

In the 1st test case, there is a cycle, from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.

In the 2nd test case, there is no cycle. The movement from index 1 -> 1 -> 1 ... is not a cycle, because the cycle's length is 1.

In the 3rd test case,  there is no cycle. The movement from index 1 -> 2 -> 1 is not a cycle, because all movements in a cycle must follow a single direction.

Sample Input 2 :

Sample Output 2 :

False
True

Hint 1

Hint 2

For each index, check If there exists a cycle passing through that index.

Approaches (2)

Approach 1

Approach 2

Brute-Force

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.

Time Complexity

O(N^2), Where N is the size of the given array.

It takes O(N) to consider every index and in the worst case, for each index, it will take O(N) time to check if there can be a cycle. Thus, the final time complexity is O(N * N) = O(N^2).

Space Complexity

O(N), Where N is the size of the given array.

O(N) extra space is needed to store the visited indices.

(100% EXP penalty)

Circular Array Loop

Console