Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Repeatedly replace n with the sum of the squares of its digits. If you reach 1, it's happy. The danger is an infinite loop — non-happy numbers fall into a cycle that never hits 1. Detect that cycle either with a hash set of seen values (O(1) extra per insert, O(log n) space) or with Floyd's fast/slow pointers on the digit-square-sum function (O(1) space). Both are correct; the set is the easy answer, Floyd's is the 'no extra memory' flex.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you realize the sequence can loop forever and reach for cycle detection — and whether you connect 'iterating a deterministic function' to the linked-list cycle problem rather than guessing at an arbitrary iteration cap.
Where candidates slip
Looping with no termination guard (infinite loop on any unhappy number), or capping iterations at a magic number like 1000 instead of actually detecting the cycle.
How to stand out
Name the framing out loud — 'next() makes this an implicit linked list, so this is Linked List Cycle' — then offer both the set solution and the O(1)-space Floyd's variant, explaining the trade.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewIterate n = sum of squares of digitsNeed O(1) extra space?NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Hash Set — Detect a Repeated Value
1Hint 1Explore hintHide hint
The process either ends at 1 or repeats a number forever. What data structure lets you notice 'I've produced this exact value before' in O(1)?
2Hint 2Explore hintHide hint
Keep a set of every value you've generated. Before computing the next value, check if the current one is already in the set.
3Hint 3Explore hintHide hint
If n == 1 → happy. If n is already in the set → you're cycling → not happy. Otherwise add n to the set and advance to next(n).
A · Core idea
Treat the sequence n, next(n), next(next(n)), … as a walk and remember every number you've visited. The instant you revisit a number, you know the walk is periodic and will never escape — so n is not happy. If you instead land on 1, it's happy.
Why a set is the natural fit. The core difficulty isn't computing the digit-square-sum — that's a simple loop. The difficulty is termination: an unhappy number iterates forever. A set converts 'have I been here before?' into an O(1) membership test, which is exactly the question that distinguishes a cycle from progress toward 1.
Why we check membership before advancing. The loop condition is while n != 1 and n not in seen. We add the current n to seen, then move to next(n). When control returns to the top, if the new n is already in seen, we've closed a loop and stop. Ordering matters: we record where we are before stepping, so the repeat is caught on the step that re-enters a visited value.
Why the values stay bounded (so this always terminates). Any number below 1000 maps, at most, to 9²×3 = 243-ish, and larger numbers shrink rapidly toward that range. So the set of reachable values is small and finite — the loop runs only a handful of iterations regardless of how large the original n is. There is no scenario where the set grows without bound.
Why this beats a magic iteration cap. A tempting hack is 'loop 1000 times and give up'. That's fragile and unprincipled — you're guessing at a bound instead of proving termination. The set proves it: a repeat is definitive evidence of a non-terminating cycle.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 19Hash-map state
n=19
19Continue scanning
record 19, next = 82
trueC · Code with teaching comments
Reference implementation previewpublic boolean isHappy(int n) { Set<Integer> seen = new HashSet<>(); while (n != 1 && !seen.contains(n)) { seen.add(n); n = next(n);Explore the full codeHide the full code
D · Why it works and complexityO(log n) timeO(log n) spaceOpen the invariant and proofExplore the proofHide the proof
The digit-square-sum function turns the integers into an implicit linked list: each number points to its unique successor. 'Is n happy?' becomes 'does this linked list end at 1, or does it have a cycle?' — literally Linked List Cycle (LC 141). Seeing that mapping is what makes the set obvious and Floyd's pointers available as an upgrade.
ComplexityO(log n) time, O(log n) space — The number of distinct values before reaching 1 or repeating is bounded — values quickly drop below ~1000 and the chain length is effectively constant, expressed as O(log n) in terms of the digit count of n. The set holds those same values → O(log n) space.
E · Edge cases and pitfalls6n = 1 — Loop body never runs (n == 1) → returns true immediately.Explore edge casesHide edge cases
Edge cases handled
n = 1Loop body never runs (n == 1) → returns true immediately.n = 77 → 49 → 97 → 130 → 10 → 1: happy. Tests a longer chain that still terminates at 1.n = 2Falls into the 4 → 16 → 37 → ... → 4 cycle; when 4 reappears in the set, returns false.
Pitfalls
- Looping with no termination guard — any unhappy number spins forever.
- Using `/` instead of `//` in Python — float division corrupts the digit extraction.
- Capping iterations at an arbitrary number instead of detecting the actual repeat.
Approach 2 of 2 · Optimal
Floyd's Fast/Slow Pointers (O(1) Space)
1Hint 1Explore hintHide hint
If next() makes the numbers an implicit linked list, then detecting 'does it loop?' is exactly the Linked List Cycle problem. What technique solves that without extra memory?
2Hint 2Explore hintHide hint
Run two pointers over the next() function: slow advances one step, fast advances two steps per iteration.
3Hint 3Explore hintHide hint
If fast reaches 1, it's happy. If slow and fast ever land on the same value, you've found a cycle → not happy. No set needed.
A · Core idea
Reuse the tortoise-and-hare cycle detection from Linked List Cycle, but the 'next pointer' is the next() digit-square-sum function instead of a .next field. slow takes one step per iteration; fast takes two. In a cyclic sequence the faster pointer eventually laps the slower one and they collide on the same value; in a happy sequence the fast pointer reaches 1 first.
Why two speeds guarantee a meeting. If the sequence enters a cycle of length C, then once both pointers are inside the cycle, each iteration closes the gap between them by exactly one (fast gains one net step per round). A gap that shrinks by one every round must hit zero, so the pointers are guaranteed to meet — that meeting is the proof of a cycle.
Why fast checks for 1, not slow. The fast pointer is the one that races ahead, so it's the first to discover the terminal value 1 if the number is happy. We test fast == 1 at the top of each round; the moment it's true we can return early without waiting for slow. Equivalently you can test both, but checking the leader is the natural place.
Why this trades memory for subtlety. The set solution is trivially correct and readable; Floyd's removes the O(log n) memory at the cost of a less obvious invariant. In an interview, lead with the set, then say 'if we need strictly O(1) space, the sequence is an implicit linked list, so Floyd's applies' — that line demonstrates pattern transfer, which is what earns the strong signal.
Why correctness still holds. The only two outcomes are 'reaches 1' and 'cycles'. Floyd's distinguishes them: reaching 1 short-circuits to true; a collision proves a cycle that (since it didn't pass through 1) means false. There's no third case to worry about.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 2 (unhappy)Interactive diagram
Picking the right approach
startBoth detect the cycle. The set is the clear default; Floyd's is the O(1)-space upgrade when memory is constrained.
falseC · Code with teaching comments
D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The leap is recognizing that next() defines successor edges, turning a number-theory question into Linked List Cycle. Once you internalize 'iterating any deterministic function = walking an implicit linked list', tortoise-and-hare becomes a reusable O(1)-space tool for every 'does this process loop?' question.
ComplexityO(log n) time, O(1) space — Same bounded chain length as the set approach → O(log n) time. Only two integer variables are kept regardless of input → O(1) space, which is the entire reason to prefer it over the set.
E · Edge cases and pitfalls6n = 1 — fast = next(1) = 1, loop condition fast != 1 is false → returns true immediately.Explore edge casesHide edge cases
Edge cases handled
n = 1fast = next(1) = 1, loop condition fast != 1 is false → returns true immediately.n = 19fast races to 1 along 19→82→68→100→1; loop exits with fast == 1 → true.n = 4Starts already inside the unhappy cycle; pointers collide → false.
Pitfalls
- Initializing slow and fast to the same value with a `while slow != fast` loop — it exits instantly before stepping; start fast one step ahead.
- Returning `slow == 1` instead of `fast == 1` — fast is the pointer that detects the terminal 1 first.
- Forgetting that fast takes TWO next() steps per round — one step degrades it to a plain loop with no cycle detection.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean isHappy(int n) { int slow = n; int fast = next(n); while (fast != 1 && slow != fast) { slow = next(slow);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1No termination guard (infinite loop)
Without remembering seen values (or running two pointers), an unhappy number like 2 cycles 4→16→37→…→4 forever and the function never returns.
Explore the code comparisonHide the code comparison
No termination guard (infinite loop)
Without remembering seen values (or running two pointers), an unhappy number like 2 cycles 4→16→37→…→4 forever and the function never returns.
Don't write this
def isHappy(self, n):
while n != 1: # never becomes 1 for unhappy n
n = next_val(n) # spins forever
return TrueWrite this instead
def isHappy(self, n):
seen = set()
while n != 1 and n not in seen:
seen.add(n)
n = next_val(n)
return n == 12Float division breaks digit extraction
In Python, `n / 10` yields a float (e.g. 1.9), so `n % 10` and the loop condition stop behaving like integer digit peeling. Use integer division `//`.
Explore the code comparisonHide the code comparison
Float division breaks digit extraction
In Python, `n / 10` yields a float (e.g. 1.9), so `n % 10` and the loop condition stop behaving like integer digit peeling. Use integer division `//`.
Don't write this
while x > 0:
d = x % 10
total += d * d
x = x / 10 # float! breaks the loopWrite this instead
while x > 0:
d = x % 10
total += d * d
x //= 10 # integer division keeps digits intactRevise
Carry the pattern into the interview
Pattern to remember
Cycle detection on the digit-square-sum sequence
Code pattern to memorize
def next(n):
total = 0
while n > 0:
d = n % 10
total += d * d
n //= 10
return total
# Set: loop until n == 1 or n in seen
# Floyd: slow = next(slow); fast = next(next(fast)); stop when they meet or fast == 1Rules to remember
- 1The sequence either reaches 1 (happy) or enters a cycle that never contains 1 (unhappy) — those are the only two outcomes, so you must detect the cycle.
- 2Compute the next value by
digit % 10squared, summed, thenn //= 10(integer division) — repeat untiln == 0. - 3With a set, check
n in seenBEFORE computing the next value; a repeat means you're looping → return false. - 4With Floyd's, advance
slowone step andfasttwo steps; if they meet at a value, it's a cycle → return false; iffasthits 1, it's happy. - 5The values stay bounded (a 3-digit number maps to at most 243), so termination is guaranteed — there's no risk of running forever.
- 6Use integer division
//in Python (not/) —/gives a float and breaks the digit loop.
Use this pattern when
- A process repeatedly transforms a number/state and you must decide if it terminates or loops
- You suspect an infinite loop and need cycle detection on an implicit 'next state' function
- The state space is bounded, so the sequence must eventually repeat
- Interviewer hints at 'no extra space' → reach for Floyd's fast/slow pointers
Choose another pattern when
- You need the actual cycle length or entry point and structure matters → full Floyd's analysis, not just detection
- State isn't a single integer / isn't deterministic → cycle detection doesn't apply
- The transform is monotonic (always increases/decreases) → it can't cycle, so no detection needed
- Memory is plentiful and clarity wins → just use the set; don't over-engineer Floyd's
Interview takeaway
Happy Number is cycle detection in disguise. The digit-square-sum is just a deterministic 'next' function, so the sequence is a linked list of numbers — and 'does it loop?' is exactly Linked List Cycle (LC 141). A hash set is the readable answer; Floyd's tortoise-and-hare is the O(1)-space upgrade. Recognize the implicit-linked-list framing and you've unlocked a whole family of problems.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCycle detection on an implicit linked list. The digit-square-sum is a deterministic next() function, so this is Linked List Cycle (LC 141) in number-theory clothing. A hash set is the readable answer; Floyd's tortoise-and-hare is the O(1)-space upgrade. Same family as Find the Duplicate Number and Linked List Cycle II.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Linked List CycleComing soonThe parent pattern — Happy Number is this exact problem with next() as the implicit pointer.
- Linked List Cycle IIComing soonFind the cycle's entry node — extends Floyd's with a second phase from the meeting point.
- Find the Duplicate NumberComing soonArray values as next() pointers — Floyd's cycle detection finds the duplicate in O(1) space.
- Add DigitsComing soonSimilar digit-folding process, but it always converges (digital root) — no cycle to detect.