Happy Number (LC 202)

Pattern: Fast & Slow Pointers (Floyd’s cycle detection on an implicit linked list)
Difficulty: Easy
Key Concept: Repeatedly map n to the sum of squares of its digits; a happy number eventually reaches 1; otherwise the sequence cycles — detect the cycle with a hash set or with two “pointers” moving at different speeds.

Problem Statement

Write an algorithm to determine if a positive integer n is a happy number.

A happy number is defined by this process:

• Start with any positive integer.
• Replace the number by the sum of the squares of its digits.
• Repeat until the number equals 1 (then it is happy), or it loops endlessly in a cycle that does not include 1 (then it is not happy).

Input: Integer n (positive).

Output: true if n is happy, false otherwise.

---

1. Algorithm & Pseudocode

Helper: sumOfSquares(n)

1. Set sum = 0.
2. While n > 0:
   • digit = n % 10
   • sum += digit * digit (use integer multiply, not Math.pow)
   • n = n / 10 (integer division)
3. Return sum.

Brute force: HashSet

1. Create empty set seen.
2. While n != 1:
   • If n is in seen, return false (infinite loop without reaching 1).
   • Insert n into seen.
   • n = sumOfSquares(n).
3. Return true.

Optimal: Floyd’s cycle detection

Treat each value as a “node”; the “next” of x is sumOfSquares(x).

1. slow = n, fast = n.
2. Repeat:
   • slow = sumOfSquares(slow) (one step)
   • fast = sumOfSquares(sumOfSquares(fast)) (two steps)
3. Until slow == fast.
4. If they meet at 1, the number is happy → return true; otherwise they met inside a non-1 cycle → return false.

(Equivalently: after the loop, return slow == 1.)

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why % 10 and / 10: The last digit of n is n % 10. Removing it is n / 10 in integer division. This walks all digits without string conversion.

Why avoid Math.pow: Math.pow returns double. Squaring digits with d * d stays in int, is exact for 0–9, and avoids casts.

Why HashSet works: The sequence is deterministic. If you revisit a value before hitting 1, you will loop forever on that cycle.

Why Floyd works: The “next pointer” graph eventually enters a cycle (either the fixed point 1 or an unhappy cycle). Two pointers, one moving twice as fast as the other, must meet inside that cycle. Meeting at 1 means you reached happiness; meeting at any other value means a cycle that never reaches 1.

Integer overflow: For typical LeetCode bounds, repeated sum-of-squares keeps values in a manageable range; int is fine here. This is unlike problems where values grow without bound.

---

3. The Dry Run

n = 19 — trace f(n) = sum of squares of digits:

n	Calculation	f(n)
19	1² + 9² = 1 + 81	82
82	8² + 2² = 64 + 4	68
68	6² + 8² = 36 + 64	100
100	1² + 0² + 0²	1

Brute force (HashSet) — state at each step:

Step	n before step	seen after	Next n
0	19	{19}	82
1	82	{19, 82}	68
2	68	{19, 82, 68}	100
3	100	{…, 100}	1
4	1	—	stop → return true

Floyd — slow moves one f, fast moves f(f(...)) per iteration:

Let f(x) = sum of squares of digits of x.

Iteration	slow (before)	fast (before)	slow (after)	fast (after)	slow == fast?
—	19	19	—	—	start
1	19	19	f(19)=82	f(f(19))=f(82)=68	no
2	82	68	f(82)=68	f(f(68))=f(100)=1	no
3	68	1	f(68)=100	f(f(1))=f(1)=1	no

Continue until slow == fast:

| 4 | 100 | 1 | f(100)=1 | f(f(1))=1 | yes (both 1) |

Loop exits with slow == fast == 1 → happy.

---

4. Java Solution

Brute Force

import java.util.HashSet;
import java.util.Set;

class Solution {

    private int sumOfSquares(int n) {
        int sum = 0;
        while (n > 0) {
            int d = n % 10;
            sum += d * d; // exact int; Math.pow returns double
            n /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1) {
            if (!seen.add(n)) {
                return false;
            }
            n = sumOfSquares(n);
        }
        return true;
    }
}

Time: Each step reduces the number of digits in practice; overall polynomial in log n per step × number of steps — effectively efficient for problem constraints.
Space: O(k) for k distinct values stored in the set.

Optimal

class Solution {

    private int sumOfSquares(int n) {
        int sum = 0;
        while (n > 0) {
            int d = n % 10;
            sum += d * d;
            n /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int slow = n;
        int fast = n;
        do {
            slow = sumOfSquares(slow);
            fast = sumOfSquares(sumOfSquares(fast));
        } while (slow != fast);
        return slow == 1;
    }
}

Time: Same asymptotic order as the set approach for typical inputs.
Space: O(1).

---

5. The “Java vs. Others” Edge

• Digit extraction: Java favors % 10 and / 10. Python solutions often use str(n) for convenience; that allocates a string — fine for interviews, but the integer loop matches Java’s strengths.
• Math.pow: Returns double; use d * d for digit squares to keep exact integer arithmetic.
• Set.add: In Java, add returns false if the element was already present — idiomatic cycle check: if (!seen.add(n)) return false;.
• Overflow: Values along the happy/unhappy sequence stay bounded for standard problem sizes; int overflow is not a practical issue here (unlike multiplying huge ints).

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(log n) amortized per transformation × iterations; bounded in practice	O(k)	HashSet remembers every visited value until repeat or 1.
Optimal (Floyd)	Same order as brute for typical n	O(1)	No auxiliary structure; same idea as cycle detection in a linked list.