Happy Number

1. The Problem

Starting with any positive integer, repeatedly replace it with the sum of the squares of its digits. A happy number eventually reaches 1. An unhappy number loops forever through a cycle that includes 4.

# 19 is happy:
# 1² + 9² = 82
# 8² + 2² = 68
# 6² + 8² = 100
# 1² + 0² + 0² = 1  ✓ → return True
#
# 2 is not happy:
# 2² = 4
# 4² = 16
# 1² + 6² = 37
# 3² + 7² = 58 → ... → 4  (cycle!)  → return False

2. The Cycle Detection Insight

This process either:

• Reaches 1 (happy), or
• Enters an infinite cycle (unhappy)

To detect a cycle, we can use a hash set (seen before?) or Floyd's slow/fast pointer applied to the sequence of numbers instead of a linked list.

3. Solution 1 — Hash Set

def is_happy(n):
    def digit_square_sum(num):
        return sum(int(d) ** 2 for d in str(num))

    seen = set()
    while n != 1:
        if n in seen:
            return False  # Cycle detected
        seen.add(n)
        n = digit_square_sum(n)
    return True

print(is_happy(19))  # True
print(is_happy(2))   # False

4. Solution 2 — Floyd's Cycle Detection (O(1) Space)

Instead of tracking seen numbers in a set, use a slow and fast pointer on the number sequence. If there's a cycle, fast will eventually lap slow. If it reaches 1, happy.

def is_happy_floyd(n):
    def next_n(num):
        return sum(int(d) ** 2 for d in str(num))

    slow = n
    fast = next_n(n)

    while fast != 1 and slow != fast:
        slow = next_n(slow)
        fast = next_n(next_n(fast))

    return fast == 1

print(is_happy_floyd(19))  # True
print(is_happy_floyd(2))   # False

5. Trace — Floyd's on n=2

# Sequence: 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ...
#                                                              ↑ cycle back to 4
# slow starts at 2, fast starts at 4
#
# Step 1: slow=4,  fast=next(next(4))=next(16)=37
# Step 2: slow=16, fast=next(next(37))=next(58)=89
# Step 3: slow=37, fast=next(next(89))=next(145)=42
# Step 4: slow=58, fast=next(next(42))=next(20)=4
# Step 5: slow=89, fast=next(next(4))=next(16)=37
# Step 6: slow=145,fast=next(next(37))=next(58)=89
# Step 7: slow=42, fast=next(next(89))=next(145)=42
# slow == fast == 42, and 42 != 1 → return False  ✓