-
Notifications
You must be signed in to change notification settings - Fork 0
/
pawn.js
46 lines (42 loc) · 1005 Bytes
/
pawn.js
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
45
46
/*
You are given an array. The value at each index represents the
index of the next value you must read. As you continue reading
these values, you will ultimately find yourself falling into a
cycle. Return the length of this cycle
Example:
A = [3,0,4,2,5,6,4]
Steps :
0,3,2,4,5,6,4,5,6,4...
Length of cycle = 3 (4,5,6)
UPDATE
Now with O(1) space
*/
function startCounting(A, currPos) {
var steps=0,
dist=0,
newPos;
for (;;) {
steps++;
newPos = A[currPos]%A.length;
dist += newPos - currPos;
if (!dist) {
return steps;
}
currPos = newPos;
}
}
function solution(A) {
var dict = {};
var currPos=0, newPos=0, steps=0;
for (;;) {
newPos = A[currPos]%A.length;
if (A[newPos]>A.length) {
return startCounting(A, newPos);
} else {
A[newPos]+=A.length;
}
currPos = newPos;
}
}
var A = [3,0,4,2,5,6,4]
console.log(solution(A));