LeetCode 202: Happy Number Solution in Python Explained

Problem Statement

In LeetCode 202: Happy Number, you’re given:

• A positive integer n.
• Your task is to return true if n is a happy number, false otherwise.

A happy number follows this process:

• Replace the number with the sum of the squares of its digits.
• Repeat until the number becomes 1 (happy) or loops endlessly (unhappy).

This is distinct from bitwise challenges like LeetCode 201: Bitwise AND of Numbers Range, focusing instead on digit manipulation and cycle detection.

Constraints

• 1 ≤ n ≤ 2³¹ - 1.

Examples

Let’s look at some cases:

Copy codeInput: n = 19
Output: true
Explanation: 
<ul>
<li>19 → 1² + 9² = 1 + 81 = 82</li>
<li>82 → 8² + 2² = 64 + 4 = 68</li>
<li>68 → 6² + 8² = 36 + 64 = 100</li>
<li>100 → 1² + 0² + 0² = 1 + 0 + 0 = 1</li>
<li>Reaches 1, so happy.</li>
</ul>

Copy codeInput: n = 2
Output: false
Explanation: 
<ul>
<li>2 → 2² = 4</li>
<li>4 → 4² = 16</li>
<li>16 → 1² + 6² = 1 + 36 = 37</li>
<li>37 → 3² + 7² = 9 + 49 = 58</li>
<li>Continues (e.g., 89, 145, 42, 20, 4), loops at 4, never reaches 1.</li>
</ul>

Copy codeInput: n = 1
Output: true
Explanation: Already 1, so happy.

These examples show we’re detecting if the process terminates at 1 or cycles.

Understanding the Problem

How do we solve LeetCode 202: Happy Number in Python? For n = 19, we compute sums of squared digits until we hit 1. For n = 2, we notice it loops (4 → 16 → 37 → … → 4). A brute-force approach might keep calculating forever, but since unhappy numbers cycle, we can detect repetition. This isn’t a grid traversal like LeetCode 200: Number of Islands; it’s about sequence analysis. We’ll use: 1. Cycle Detection with Hash Set: O(log n) time, O(log n) space—our best solution. 2. Floyd’s Cycle-Finding Algorithm: O(log n) time, O(1) space—an alternative.

Let’s explore the best solution.

Best Solution: Cycle Detection with Hash Set Approach

Explanation

The Cycle Detection with Hash Set approach tracks numbers we’ve seen:

• Compute the sum of squares of digits for n.
• If it’s 1, return true.
• If it’s already in a set, we’ve found a cycle, return false.
• Otherwise, add it to the set and repeat.

This runs in O(log n) time (the number of steps to reach 1 or a cycle is logarithmic due to digit reduction) and uses O(log n) space for the set. It’s intuitive and reliable, making it our best solution.

For n = 19, it reaches 1. For n = 2, it detects the cycle at 4.

Step-by-Step Example

Example 1: n = 19

Goal: Return true.

• Step 1: Initialize.
• n = 19, seen = set().
• Step 2: Process numbers.
• 19: Not in seen, add 19, compute 1² + 9² = 82.
• 82: Not in seen, add 82, compute 8² + 2² = 68.
• 68: Not in seen, add 68, compute 6² + 8² = 100.
• 100: Not in seen, add 100, compute 1² + 0² + 0² = 1.
• 1: Equals 1, stop.
• Output: true.

Example 2: n = 2

Goal: Return false.

• Step 1: n = 2, seen = set().
• Step 2:
• 2: Add 2, 2² = 4.
• 4: Add 4, 4² = 16.
• 16: Add 16, 1² + 6² = 37.
• 37: Add 37, 3² + 7² = 58.
• 58: Add 58, 5² + 8² = 89.
• 89: Add 89, 8² + 9² = 145.
• 145: Add 145, 1² + 4² + 5² = 42.
• 42: Add 42, 4² + 2² = 20.
• 20: Add 20, 2² + 0² = 4.
• 4: In seen, cycle detected.
• Output: false.

How the Code Works (Cycle Detection with Hash Set) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codedef isHappy(n: int) -> bool:
    # Line 1: Initialize set to track seen numbers
    seen = set()
    # Empty set to store computed sums (e.g., set())

    # Line 2: Loop until cycle or 1 is found
    while n != 1 and n not in seen:
        # Continue if not happy and no cycle
        seen.add(n)
        # Add current number (e.g., 19)

        # Line 3: Compute sum of squares of digits
        sum_squares = 0
        # Reset sum for new calculation (e.g., 0)
        while n > 0:
            # Process each digit
            digit = n % 10
            # Get rightmost digit (e.g., 19 % 10 = 9)
            sum_squares += digit * digit
            # Add square (e.g., 9² = 81)
            n //= 10
            # Remove digit (e.g., 19 // 10 = 1)
        n = sum_squares
        # Update n (e.g., 82)

    # Line 4: Return result
    return n == 1
    # True if 1, False if cycle (e.g., n = 1)

This solution is clear and efficient for detecting happiness.

Alternative: Floyd’s Cycle-Finding Algorithm Approach

Explanation

Floyd’s Cycle-Finding Algorithm (or "tortoise and hare") uses two pointers:

• Slow pointer moves one step (sum of squares once).
• Fast pointer moves two steps (sum of squares twice).
• If they meet, there’s a cycle (false).
• If slow reaches 1, it’s happy (true).

It’s O(log n) time (steps to cycle or 1) and O(1) space (no extra storage), making it space-efficient.

Step-by-Step Example

For n = 19:

• Slow = 19, Fast = 82.
• Slow = 82, Fast = 100.
• Slow = 100, Fast = 1.
• Slow = 1, Fast = 1, happy.

For n = 2:

• Slow = 4, Fast = 16.
• Eventually meet at 4, cycle.

How the Code Works (Floyd’s)

Copy codedef isHappyFloyd(n: int) -> bool:
    def get_next(num):
        total = 0
        while num > 0:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total

    slow = n
    fast = get_next(n)
    while fast != 1 and slow != fast:
        slow = get_next(slow)
        fast = get_next(get_next(fast))
    return fast == 1

Complexity

• Cycle Detection with Hash Set:
• Time: O(log n) – steps to 1 or cycle.
• Space: O(log n) – set size.
• Floyd’s Cycle-Finding Algorithm:
• Time: O(log n) – steps to 1 or cycle.
• Space: O(1) – two pointers.

Efficiency Notes

Cycle Detection with Hash Set is our best solution for its clarity and simplicity, despite O(log n) space. Floyd’s algorithm saves space with O(1), ideal when memory is tight.

Key Insights

• Happy: Reaches 1.
• Unhappy: Cycles (e.g., 4, 16, 37…).
• Detection: Set or pointers.

Additional Example

For n = 7:

• 7 → 49 → 97 → 130 → 10 → 1, happy.

Edge Cases

• n = 1: true.
• Large n: Cycles or 1, both handle it.

Final Thoughts

LeetCode 202: Happy Number in Python is a fun exploration of digits and cycles. Cycle Detection with Hash Set offers an intuitive solution, while Floyd’s algorithm impresses with space efficiency. Want more? Try LeetCode 141: Linked List Cycle for cycle detection or LeetCode 204: Count Primes for number fun. Test your skills—Solve LeetCode 202 on LeetCode with n = 19 (expecting true)—find happiness in numbers today!