You are given a circular array
arr[]
of positive and negative integers. If a number
k
at an index is positive, then move forward
k
steps. Conversely, if it's negative (
-k
), move backward
k
steps. Write a program to
determine if there is a loop (or a cycle)
in
arr[]
.
Problem Note
- Since the array is circular, you may assume that the last element's next element is the first element, and the first element's previous element is the last element.
- A cycle must start and end at the same index.
- Cycle's length > 1.
- Movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.
Example 1
Input: arr[] = [2,-1,2,2,1]
Output: true
Explanation: There is a cycle, from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.
Example 2
Input: arr[] = [1, 1, 1, 1, 1, 1]
Output: true
Explanation: Whole array forms a cycle.
Example 3
Input: A[] = [-2,1,-1,-2,-2]
Output: false
Explanation: The movement from index 1 -> 2 -> 1 -> ... is not a cycle, because movement from index 1 -> 2 is a forward movement, but movement from index 2 -> 1 is a backward movement. All movements in a cycle must follow a single direction.