Edit Problem

Title

Problem URL

Difficulty

Tags

Fast & Slow Pointers

Go file path (optional)

Notes (optional)

## What It Does

A "happy number" is one where repeatedly replacing it with the sum of squares of its digits eventually reaches `1`. Unhappy numbers fall into an infinite cycle that never includes `1` — and that's the key insight this solution exploits: **it reframes the problem as cycle detection**.

`squared_sum` extracts each digit via `% 10` and accumulates its square, then strips the digit with `/ 10`. The main function runs Floyd's tortoise-and-hare on the sequence of `squared_sum` calls — `slow` advances one step, `fast` advances two. If the number is unhappy, the sequence cycles and `slow == fast` triggers the `break`. If it's happy, `fast` hits `1` and the loop condition exits naturally. Either way, `fast == 1` is the final verdict.

For example, `19` → `1² + 9² = 82` → `6² + 4² + ... = 68` → ... → `1`, returning `true`. For `2`, the sequence eventually loops back on itself without hitting `1`, returning `false`.

---

## Complexity Analysis

**Time Complexity: O(log n)**
Each call to `squared_sum` reduces a number with `d` digits in O(d) = O(log n) time. The number of steps before hitting `1` or entering a cycle is bounded by a small constant in practice (the cycle for unhappy numbers is known to always contain `4`), so the overall complexity is effectively O(log n).

**Space Complexity: O(1)**
Just two integers — `slow` and `fast`. No sets, no history stored.

---

## A Few Notes

**The textbook approach uses a hash set.** Store each seen value; if you hit a repeat, it's unhappy. That's O(n) space. This solution gets O(1) by recognizing that an infinite sequence *must* cycle — making it a perfect Floyd's application outside the usual linked list context.

**The loop condition `fast != 1` is slightly fragile.** If `fast` somehow skips over `1` — which mathematically can't happen here since `squared_sum(1) == 1` is a fixed point — the loop would run forever. It's safe, but an alternative guard of `fast != 1 && slow != fast` in the condition (instead of a `break`) would make the termination logic more self-contained and readable.

**This is a good example of pattern recognition over problem-specific logic.** The happy number sequence isn't *obviously* a linked list, but anything that can be modeled as a deterministic sequence with finite state can be treated as one — and Floyd's applies. Spotting that abstraction is the real skill here.

First solved

May 28, 2026