Skip to content

Instantly share code, notes, and snippets.

@VegaFromLyra
Created June 9, 2015 01:30
Show Gist options
  • Save VegaFromLyra/90ad80ad31141095b0b2 to your computer and use it in GitHub Desktop.
Save VegaFromLyra/90ad80ad31141095b0b2 to your computer and use it in GitHub Desktop.
Single complete cycle
using System;
// Determine whether a circular array of relative indices is composed
// of a single complete cycle
// ToDO - Do it O(1) space
namespace SingleCompleteCycle
{
public class Program
{
public static void Main(string[] args)
{
test(new int[]{ 2, 2, -1 });
test(new int[]{ 1, -2, 1 });
test(new int[]{ 1, 2, 3 });
test(new int[]{ 1, -6, 7, 2 });
test(new int[]{ -6, 1, 3 });
}
static void test(int[] arr) {
Console.WriteLine("Is SCC: {0}", isSCC(arr));
}
static bool isSCC(int[] arr) {
if (arr.Length == 0) {
return false;
}
bool[] visited = new bool[arr.Length];
int current = 0;
int count = 0;
while (count < arr.Length) {
if (current >= 0) {
current = (current + arr[current]) % arr.Length;
}
while (current < 0) {
current += arr.Length;
}
visited[current] = true;
count++;
}
for(int i = 0; i < visited.Length; i++) {
if (!visited[i]) {
return false;
}
}
return true;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment