Skip to content

169 — Happy Number

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

169 — Happy Number

LeetCode 202 · Easy. A happy number is defined by this process: starting with any positive integer, replace it with the sum of the squares of its digits, and repeat. The number is happy if this eventually reaches 1. If it instead loops forever in a cycle that never includes 1, the number is not happy. Given an integer n, return true if it's happy.

🍽️ Intuition

Picture a number bouncing between values, like a pinball following its own digit-squaring rule: 19 -> 1² + 9² = 82 -> 8² + 2² = 68 -> 6² + 8² = 100 -> 1² + 0² + 0² = 1. Landed on 1 — happy. But try 2: 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 — and there's 4 again, a number we've already visited. From here the pinball just retraces the exact same loop forever, never touching 1. The whole question boils down to one thing: does this bouncing sequence hit 1, or does it start repeating a value it's already seen (meaning it's stuck in a loop that will never include 1)?

19 -> 82 -> 68 -> 100 -> 1                    (happy: reaches 1)

2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4   (unhappy: 4 repeats -> stuck in a cycle)
     ^________________________________________________|

🚩 Pattern-Recognition Cue

"Repeat this transformation until you reach a fixed value, or detect that you're stuck in a loop" is the cycle-detection signal. Whenever a sequence is generated by repeatedly applying a deterministic function to the current value (not by walking a real data structure), and the question is "does it reach X, or does it cycle forever," reach for either a "have I seen this before?" set, or — since the sequence behaves exactly like a linked list where each value's next is sumOfSquares(value) — Floyd's fast/slow pointer trick.

🐢 Brute Force

Repeatedly apply the sum-of-squares-of-digits transformation, tracking every value seen in a set. Stop when the value is 1 (happy) or the value repeats one already seen (unhappy — it's cycling).

func sumOfSquares(_ n: Int) -> Int {
    var num = n
    var sum = 0
    while num > 0 {
        let digit = num % 10
        sum += digit * digit
        num /= 10
    }
    return sum
}

func isHappyBruteForce(_ n: Int) -> Bool {
    var seen = Set<Int>()
    var num = n

    while num != 1 && !seen.contains(num) {
        seen.insert(num)
        num = sumOfSquares(num)
    }

    return num == 1
}

// smoke test
print(isHappyBruteForce(19))   // true
print(isHappyBruteForce(2))    // false
print(isHappyBruteForce(1))    // true
print(isHappyBruteForce(7))    // true

Big-O: O(log n) time to reach either 1 or a cycle (each application of sumOfSquares shrinks the number toward a small range within a bounded number of steps). O(log n) space for the seen set of previously visited values.

🚀 Optimal

Treat the sequence of values as an implicit linked list, where each value's "next" is sumOfSquares(value). Run a slow pointer that takes one step at a time and a fast pointer that takes two — if the sequence is happy, fast reaches 1 first; if it's cycling, fast and slow are guaranteed to eventually land on the exact same value.

func isHappy(_ n: Int) -> Bool {
    var slow = n
    var fast = sumOfSquares(n)

    while fast != 1 && slow != fast {
        slow = sumOfSquares(slow)
        fast = sumOfSquares(sumOfSquares(fast))
    }

    return fast == 1
}

// smoke test — same cases as the brute force
print(isHappy(19))   // true
print(isHappy(2))    // false
print(isHappy(1))    // true
print(isHappy(7))    // true

Big-O: O(log n) time — same shrinking argument as the brute force, but the fast pointer catches the slow one within one cycle length instead of needing to remember every value. O(1) space — no set required.

🔑 The Key Insight

The brute force's seen set is really just a way of asking "has this exact value shown up before?" — but that question has a classic O(1)-space answer whenever the sequence is generated by repeatedly applying a fixed function: Floyd's cycle detection. A slow pointer moving one step and a fast pointer moving two steps are guaranteed to meet if and only if the sequence loops, because the fast pointer gains exactly one step of "lead" on the slow pointer every iteration, so once both are inside the cycle, the gap between them shrinks by one each time until it hits zero. No memory of the whole path is needed — only two positions moving at different speeds.

🔗 Related Chapters

  • Hash Maps and Hash Sets — the seen set powering the brute force's "have I visited this value before?" check.
  • Fast and Slow Pointers — the optimal's Floyd's-cycle-detection approach, applied here to an implicit sequence of values rather than a real linked list.

🧸 Memory Sentence

Happy Number is a pinball bouncing between digit-square sums — it either lands on 1, or it starts retracing a loop it's already been in, and a fast/slow pointer catches that loop without remembering the whole path.

✅ Check Your Understanding

  1. Why is it guaranteed that this process either reaches 1 or eventually revisits some earlier value, rather than producing an infinite stream of never-before-seen numbers?
  2. In the optimal solution, fast starts one step ahead of slow (fast = sumOfSquares(n) while slow = n). Why does the loop condition check fast != 1 but not also check slow != 1 directly?
  3. Walk through why slow and fast are mathematically guaranteed to become equal if the sequence cycles, even though fast moves twice as fast and could conceivably "jump over" slow without ever landing on the same value.
  4. The brute force's O(log n) space bound comes from the seen set holding only distinct values along the path before a repeat. Why doesn't this set need to be arbitrarily large, given that n could be any positive integer?

⬅️ Previous: Set Matrix Zeroes · Next: Plus One ➡️

Clone this wiki locally