Fast and Slow Pointers Example: A Code Generator That Starts Repeating

Each code is computed from the one before, so the codes form a list that exists only as a function, and the two speeds find the repeat without storing any code.

Fast and slow pointers work on any sequence in which each value fixes the next, even one with no list and no nodes, because a repeated value means the sequence cycles from there on. A door lock generates its next code from the current one with next(x) = (x² + 1) mod 11, where mod 11 is the remainder after dividing by 11, starting from 3. Nothing in the question mentions a list: the cue is that the next code depends only on this one, so next_code(x) plays the part of node.next, and there are only 11 possible codes, so the sequence has to repeat. The codes run 3 10 2 5 4 6 and onward.

Which code is the first to come round again?

After 4 comes 6, and (6² + 1) mod 11 = 37 mod 11 = 4, so the codes cycle 4 6 4 6 from there.

Both phases run on the codes as they do on a list: the first until slow and fast are equal, and the second from the start value and the meeting value, one step each, until they are equal again. The trace shows each code once, in the order generated, with the cycle from 6 back to 4 in the input.

Both phases on the codes from 3

Input3 → 10 → 2 → 5 → 4 → 6 → 4

Start: both on 3
1. 3slowfast
2. 10
3. 2
4. 5
5. 4
6. 6
Both start on 3
Move 1: slow 10, fast 2
1. 3
2. 10slow
3. 2fast
4. 5
5. 4
6. 6
Slow on 10, fast two codes ahead on 2
Move 2: slow 2, fast 4
1. 3
2. 10
3. 2slow
4. 5
5. 4fast
6. 6
Fast reaches 4, the start of the cycle
Move 3: slow 5, fast 4
1. 3
2. 10
3. 2
4. 5slow
5. 4fast
6. 6
Fast goes round 6 and back to 4
Move 4: slow 4, fast 4
1. 3
2. 10
3. 2
4. 5
5. 4slowfast
6. 6
Slow arrives on 4 and the two meet
Phase 2: slow back on 3, fast on 4
1. 3slow
2. 10
3. 2
4. 5
5. 4fast
6. 6
Phase 2: slow restarts at 3, fast stays on 4
Step 1: slow 10, fast 6
1. 3
2. 10slow
3. 2
4. 5
5. 4
6. 6fast
Each moves one code
Step 2: slow 2, fast 4
1. 3
2. 10
3. 2slow
4. 5
5. 4fast
6. 6
Fast is back on 4 while slow is still in the tail
Step 3: slow 5, fast 6
1. 3
2. 10
3. 2
4. 5slow
5. 4
6. 6fast
Fast goes round once more
Step 4: slow 4, fast 4
1. 3
2. 10
3. 2
4. 5
5. 4slowfast
6. 6
Both reach 4 together: the first code to repeat

ResultThe first code to repeat is 4, and the cycle holds 2 codes.

Here the meeting point happened to be the first repeated code; the second phase is what proves it, and on most sequences the two differ. The listing replaces every .next with a call to next_code.

code_generator.pypy

def next_code(x):
    return (x * x + 1) % 11


def first_repeat(start):
    slow = fast = start
    while True:
        slow = next_code(slow)
        fast = next_code(next_code(fast))
        if slow == fast:
            break
    slow = start
    while slow != fast:
        slow = next_code(slow)
        fast = next_code(fast)
    return slow


def cycle_length(start):
    repeat = first_repeat(start)
    length = 1
    code = next_code(repeat)
    while code != repeat:
        code = next_code(code)
        length += 1
    return length


codes = [3]
for _ in range(7):
    codes.append(next_code(codes[-1]))
print("codes:", *codes)
print("first code to repeat:", first_repeat(3))
print("codes in the cycle:", cycle_length(3))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

codes: 3 10 2 5 4 6 4 6
first code to repeat: 4
codes in the cycle: 2

The comparison here is by value, slow == fast, where a list compares nodes by identity, and both are right: a code fixes every code after it, so two equal codes are the same point in the sequence, while two list nodes can hold the same value and still be different nodes. The walk is O(a + L) calls for a tail of a codes and a cycle of L, with no code stored; a set of seen codes would find the same 4 with O(a + L) memory. The while True is safe only because the codes are bounded, so a repeat must come; a sequence that could grow for ever would need a limit on the number of moves.

← → move through sections and cards