package algoexpert.medium;

/*

PROBLEM:

Find if single cycle exists in given array

-> starting at any index and following the jumps, every element is visited exactly once before landing back on the starting index

EXAMPLE:

[2,3,1,-4,-4,2] -> true

Solution:

1. HashMap -> time : O(n) | space : O(n)

2. Count visited -> time : O(n) | space : O(1) [we don't really need hashmap, just need to check if it is revisiting 0 only at end]

*/

public class SingleCycleCheck

{

public static void test()

{

System.out.println(hasSingleCycle(new int [] {2,3,1,-4,-4,2}));

System.out.println(hasSingleCycle(new int [] {1,1,1,1,2}));

}

public static int nextIndex(int current, int [] array)

{

int next = (current + array[current]) % array.length;

if (next < 0) { next = array.length + next; }

return next;

}

public static boolean hasSingleCycle(int[] array) {

if (array.length < 1) { return true; }

int visitedCount = 0;

int current = 0;

while (visitedCount < array.length)

{

if (visitedCount > 0 && current == 0) { return false; }

visitedCount += 1;

current = nextIndex(current, array);

}

return (current == 0) ? true : false;

}

}