Cycle Detection
What is this?
Some processes step from one state to the next in a fixed, repeatable way. If such a process ever lands on a state it has visited before, it is stuck in a loop and will repeat forever. The trick here is to remember every state you have seen in a hash set, so the moment one shows up twice you have caught the loop — just like noticing you have walked past the same shop twice and realizing you are going in circles.
💡 Fun fact: There is a clever alternative that needs almost no memory — Floyd's "tortoise and hare", where one pointer moves twice as fast as the other and they are guaranteed to collide inside any loop. Robert Floyd, who won the Turing Award, is credited with it, though he never published the algorithm himself.
🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.
Core idea: When a process moves deterministically from one state to the next, it either reaches a goal or revisits a state it's already been in — and a revisit means it will loop forever. A set of seen states detects that loop; fast/slow pointers detect it in O(1) space.
The shape
If you ever see the same state twice, the future repeats — so:
- Seen-set: record each state; stop on the goal (success) or on a repeat (cycle). O(states) time and space.
- Floyd's tortoise & hare: a slow pointer (1 step) and fast pointer (2 steps) over
next(); if they meet, there's a cycle — O(1) space.
The problem
- Happy Number — repeatedly replace
nwith the sum of squares of its digits; it reaches 1 (happy) or falls into a fixed cycle. A seen-set spots the repeat; fast/slow does it without storing states.
Key takeaways
- Deterministic next-state ⇒ either a goal or a cycle — and a repeated state proves the cycle.
- Seen-set is the simplest detector (O(n) space); fast/slow trades it down to O(1).
- The same pattern appears on linked lists (Linked List Cycle) and any functional graph.
- Why interviewers like it: it tests whether you recognize "this will loop" and know two ways to catch it.
Problem: Happy Number.
Happy Number
Core idea: Repeatedly summing the squares of a number's digits is a deterministic step — each number leads to exactly one next number. So the process is a chain that must eventually either land on
1(happy) or step onto a number it has already produced (a cycle → not happy). The whole problem is cycle detection on that chain, and you get two tools for it: a seen set (O(k)space) or Floyd's tortoise-and-hare (O(1)space).
Problem, rephrased
You're handed a positive integer and a strange little machine. Press the button and the machine replaces your number with the sum of the squares of its digits. For example, 19 → 1² + 9² = 1 + 81 = 82. Keep pressing.
A number is happy if, by pressing the button over and over, you eventually reach 1 (and once you hit 1, you stay at 1 forever, since 1² = 1). A number is unhappy if it never reaches 1 — instead it falls into a loop that cycles forever without ever touching 1.
Your job: given n, return True if n is happy, False otherwise.
Input n |
Process | Output | Why |
|---|---|---|---|
19 |
19 → 82 → 68 → 100 → 1 |
True |
reaches 1 |
2 |
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 … |
False |
re-enters 4 — a loop, never 1 |
7 |
7 → 49 → 97 → 130 → 10 → 1 |
True |
reaches 1 |
1 |
already 1 |
True |
the happiest number |
The single button-press — "replace n with the sum of the squares of its digits" — is a fixed function. Call it next_number(n). Everything below is about following next_number and noticing when it loops.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson