-
Notifications
You must be signed in to change notification settings - Fork 232
/
single-cycle-check.py
44 lines (38 loc) · 923 Bytes
/
single-cycle-check.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# SINGLE CYCLE CHECK
# O(N) time and O(1) space
def hasSingleCycle(array):
# Write your code here.
i = 0
while array[i] != None:
jump = array[i]
array[i] = None
if jump >= 0:
i = (jump + i) % len(array)
else:
jump = abs(jump) % len(array)
if i - jump < 0:
i = len(array) + (i - jump)
else:
i -= jump
if i != 0:
return False
print(array)
for x in array:
if x != None:
return False
return True
# O(N) time and O(1) space
def hasSingleCycle(array):
# Write your code here.
visited = 0
currentIndex = 0
while visited < len(array):
if visited > 0 and currentIndex == 0:
return False
visited += 1
currentIndex = getNextIndex(currentIndex, array)
return currentIndex == 0
def getNextIndex(currentIndex, array):
jump = array[currentIndex]
nextIndex = (currentIndex + jump) % len(array)
return nextIndex if nextIndex >= 0 else nextIndex + len(array)