LeetCode 202 · Math & Geometry · concepts: fast-slow-pointers, math-and-geometry
Problem
Repeatedly replace a number with the sum of the squares of its digits. It’s “happy” if this reaches 1; otherwise it loops forever. Return whether n is happy.
19 -> 1²+9²=82 -> 68 -> 100 -> 1 -> true
The insight — it’s cycle detection
The transformation n → sum of digit squares is a deterministic “next” function, so the sequence is effectively a linked list. It either reaches 1 or enters a cycle — exactly Linked List Cycle. Detect the loop with a seen set, or with Floyd’s fast/slow for O(1) space.
def isHappy(n):
def next_num(x):
return sum(int(d) ** 2 for d in str(x))
slow, fast = n, next_num(n)
while fast != 1 and slow != fast: # stop at 1 (happy) or a meeting (cycle)
slow = next_num(slow)
fast = next_num(next_num(fast))
return fast == 1Time O(log n) per step, space O(1) with Floyd’s (O(log n) with a set).
Why it must terminate
For any starting number, the digit-square-sum sequence is bounded (large numbers shrink toward ≤ 3-digit values), so by pigeonhole it must eventually repeat — either hitting 1 or cycling. That guarantee is what lets cycle detection decide happiness: reach 1 → happy; meet fast=slow first → unhappy.
Key insight
A deterministic “next value” sequence that might loop → cycle detection (set or Floyd’s). Recognizing a numeric sequence as a linked list — where next is an arithmetic function — is the same leap as Find the Duplicate Number, applied to math.
Related
- concepts: fast-slow-pointers, math-and-geometry
- relative: Linked List Cycle
- prev: Set Matrix Zeroes · next: Plus One
Software engineering
Infrastructure & security
Computer science
Hardware & engineering