Created
June 9, 2015 01:30
-
-
Save VegaFromLyra/90ad80ad31141095b0b2 to your computer and use it in GitHub Desktop.
Single complete cycle
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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