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.