Happy Number Explained: HashSet vs Floyd’s Cycle Detection (Optimized Approach)

Happy Number – HashSet vs Floyd’s Cycle Detection

The Happy Number problem looks simple at first, but it hides an important algorithmic concept: cycle detection. In this post, we’ll explore two valid approaches to solve the problem and understand why the optimized solution works.

📌 Complete Python solution code: View on GitHub

---

Problem Overview

A number is called happy if repeatedly replacing it with the sum of the squares of its digits eventually leads to 1. If the process enters a cycle that does not include 1, the number is not happy.

Example:

• 19 → 1² + 9² = 82
• 82 → 8² + 2² = 68
• 68 → 6² + 8² = 100
• 100 → 1² + 0² + 0² = 1 ✅

---

Approach 1: Using a HashSet

The most commonly taught approach uses a HashSet to track numbers we have already seen. If a number repeats, we know we are stuck in a cycle.

Idea

• Store every generated number in a set
• If the number becomes 1 → happy
• If the number repeats → cycle detected

Code

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()
        while n != 1:
            if n in seen:
                return False
            seen.add(n)
            n = sum(int(d) ** 2 for d in str(n))
        return True

---

Approach 2: Floyd’s Cycle Detection (Slow & Fast Pointers)

Instead of storing previous values, we can observe an important pattern:

The transformation from one number to the next is deterministic, which means it must eventually form a cycle.

This is exactly the same situation as detecting a cycle in a linked list.

Idea

• Use two pointers:
  • Slow moves one step
  • Fast moves two steps
• If fast reaches 1 → happy number
• If slow meets fast at a value other than 1 → cycle detected

Code

from functools import lru_cache

class Solution:
    @staticmethod
    @lru_cache(maxsize=128)
    def squarer(x):
        if x < 10:
            return x * x
        result = 0
        while x > 0:
            result += (x % 10) ** 2
            x //= 10
        return result

    def isHappy(self, n: int) -> bool:
        slow = n
        fast = n

        while True:
            slow = self.squarer(slow)
            fast = self.squarer(fast)
            fast = self.squarer(fast)

            if fast == 1:
                return True
            if slow == fast:
                return False

---

HashSet vs Floyd’s Cycle Detection

Aspect	HashSet Approach	Floyd’s Algorithm
Concept	Track visited states	Detect cycle using pointers
Time Complexity	O(log n)	O(log n)
Space Complexity	O(n)	O(1)
Ease of Implementation	Very easy	Moderate
Pattern Reusability	Low	High
Interview Impression	Acceptable	Strong

---

Final Thoughts

This problem is not really about digits or squares. It is about identifying cycles in a deterministic process. Once that insight clicks, applying Floyd’s algorithm becomes natural.

That shift — from problem-solving to pattern recognition — is what leads to cleaner and more optimized solutions.