Problem Definition

LeetCode Link: 202. Happy Number

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

A happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits.
  • Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
  • Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2:

Input: n = 2
Output: false

Constraints:

  • 1 <= n <= 231 - 1

Thought Process

At first glance, the problem may look purely mathematical, but it’s fundamentally about detecting cycles in a sequence. Once you start calculating the sum of the squares of digits repeatedly, there are two possible outcomes:

  • You eventually reach 1, confirming the number is happy.
  • You enter a loop without reaching 1, confirming the number is unhappy.

To detect loops, we can leverage data structures like a hash set (or dictionary-like behavior), arrays, or even a two-pointer technique. Storing previously seen values allows us to identify when we’ve fallen into a cycle.

Solution 1 - Using a Dictionary (or Set)

class SolutionUsingSet:
    def isHappy(self, n: int) -> bool:        
        record = set()

        while True:
            n = self.get_sum(n)
            if n == 1:
                return True
            
            if n in record:
                return False
            record.add(n)

    def get_sum(self, n: int) -> int: 
        new_num = 0
        while n:
            n, r = divmod(n, 10)
            new_num += r ** 2
        return new_num

How It Works

  1. Initialize a set to record numbers we've computed.
  2. Calculate the sum of the squares of the current number’s digits.
  3. If the result is 1, the number is happy.
  4. If the result is already in the set, a cycle is detected—return false.
  5. Otherwise, keep adding results to the set and continue until one of the above conditions occurs.

Code Explanation

  • get_sum(n) calculates the sum of the squares of n's digits.
  • divmod(a, b) is a Python function that returns a tuple of two numbers: the quotient and remainder when a is divided by b.
  • In isHappy, we loop until we find 1 or a repeated sum.
  • If repeated, return false; if 1, return true.

Complexity Analysis

  • Time Complexity: O(log n) on average, as the sequence of sums decreases or cycles quickly.
  • Space Complexity: O(log n) due to storing intermediate values in the set.

Solution 2 - Using Arrays as Hash Maps

class SolutionUsingArray:
    def isHappy(self, n: int) -> bool:
        record = []
        while n not in record:
            record.append(n)
            new_num = 0
            for i in str(n):
                new_num += int(i)**2
            
            if new_num == 1:
                return True
            else:
                n = new_num
        return False

How It Works

This approach is conceptually similar to using a set, but we store seen values in a list. While not as efficient for lookups, the problem’s nature ensures that cycles emerge quickly and remain small.

  1. Keep track of encountered sums in a list.
  2. If you reach 1, return true.
  3. If a new sum is already in the list, return false.

Code Explanation

  • Convert the number to a string to iterate over digits easily.
  • Compute the sum of squares.
  • Check if it’s 1, or if it already exists in the list.

Complexity Analysis

  • Time Complexity: O(k), where k is the length of the cycle or steps to reach 1. List lookups are O(k), but k is small.
  • Space Complexity: Similar to using a set, O(k).

Solution 3 - A More Pythonic Set-Based Approach

How It Works

This solution is simply a cleaner, more concise version of the set-based approach. It uses Python’s expressive syntax to compute the sum of squares in a single line.

  1. While n is not 1, compute n as the sum of the squares of its digits.
  2. If we detect a repeat, return false.
  3. If we hit 1, return true.
class SolutionUsingSetSimplified:
    def isHappy(self, n: int) -> bool:
        seen = set()
        while n != 1:
            n = sum(int(i)**2 for i in str(n))
            if n in seen:
                return False
            seen.add(n)
        return True

Code Explanation

  • We use a generator expression sum(int(i)**2 for i in str(n)) to calculate the sum quickly.
  • A set seen tracks encountered numbers.

Complexity Analysis

  • Time Complexity: O(log n) as before.
  • Space Complexity: O(log n).

Additional Approach - Fast and Slow Pointer (Floyd’s Cycle Detection)

class SolutionUsingFastSlowPointer:
    def isHappy(self, n: int) -> bool:
        slow = n
        fast = n
        while True:
            slow = self.get_sum(slow)
            fast = self.get_sum(self.get_sum(fast))
            
            if slow == 1 or fast == 1:
                return True
            
            if slow == fast:
                return False

    def get_sum(self, n: int) -> int:
        new_num = 0
        while n > 0:
            n, r = divmod(n, 10)
            new_num += r ** 2
        return new_num

How It Works

Instead of relying on extra storage, we can detect cycles using a classic two-pointer technique (often used in linked list cycle detection):

  1. Define a function get_sum(n) to get the sum of the squares of the digits.
  2. Maintain two values: slow and fast.
    • slow moves through the sequence one step at a time.
    • fast moves two steps at a time.
  3. If fast or fast’s next move ever equals 1, we found a happy number.
  4. If slow and fast pointers meet (equal each other) before finding 1, it means there is a cycle—return false.

This technique doesn’t need a set or list, thus saving space.

Code Explanation

  • Move slow by calling get_sum once per iteration.
  • Move fast by calling get_sum twice per iteration.
  • If they meet, cycle detected → not happy.
  • If fast (or a double iteration of fast) hits 1, we’re done → happy.

Complexity Analysis

  • Time Complexity: O(log n), as before, since the sequence either collapses to 1 or quickly forms a cycle.
  • Space Complexity: O(1), no additional data structures required.

Key Takeaways

  1. Cycle Detection is the Core Concept:
    The crux of solving this problem is realizing that if a number is not happy, it will fall into a cycle of repeated values. Detecting that cycle is critical.
  2. Multiple Approaches, Same Goal:
    All solutions—whether using sets, arrays, or the fast-slow pointer method—aim to detect loops in the sequence of transformed numbers.
  3. Data Structure Selection:
    Using a set is the most straightforward approach, offering quick lookups and easy detection of repeats. The fast and slow pointer approach is an elegant way to detect cycles without extra space.
  4. Efficiency:
    Although the complexity can vary slightly, all methods run efficiently enough in practice. The transformations quickly stabilize or form cycles among relatively small numbers.

In conclusion, the Happy Number problem is a clever exercise in identifying cycles within a number transformation process. With multiple approaches available, you can choose the one that best fits your coding style—be it using a hash set for intuitive tracking or employing the fast-slow pointer method for constant space optimization.