Happy Number

Problem

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:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2^31 - 1

Solution

Approach 1: Hash Set for Cycle Detection

The key insight is that if we enter a cycle (see a number we’ve seen before), it’s not a happy number.

Implementation

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(num):
            total = 0
            while num > 0:
                digit = num % 10
                total += digit * digit
                num //= 10
            return total

        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = get_next(n)

        return n == 1

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

class Solution:
    def isHappy(self, 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

Approach 3: Hardcoded Cycle Detection

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(num):
            total = 0
            while num > 0:
                digit = num % 10
                total += digit * digit
                num //= 10
            return total

        # Known cycle that unhappy numbers eventually enter
        cycle_members = {4, 16, 37, 58, 89, 145, 42, 20}

        while n != 1 and n not in cycle_members:
            n = get_next(n)

        return n == 1

Approach 4: Using String Conversion

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(num):
            return sum(int(digit) ** 2 for digit in str(num))

        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = get_next(n)

        return n == 1

Complexity Analysis

Hash Set Approach:

Time Complexity: O(log n), the number of digits in n determines how many iterations.
Space Complexity: O(log n) for the set storing seen numbers.

Floyd’s Cycle Detection:

Time Complexity: O(log n)
Space Complexity: O(1), no extra space needed.

Key Insights

Cycle Guarantee: If a number is not happy, it will eventually enter a cycle. The most common cycle is {4, 16, 37, 58, 89, 145, 42, 20}.
Linked List Analogy: This problem is analogous to detecting a cycle in a linked list where each number points to its next value.
Floyd’s Algorithm: Can detect cycles without extra space using fast and slow pointers.
Digit Sum of Squares: The next number is always the sum of squares of digits.
Mathematical Property: For any number, the sequence will either reach 1 or enter a cycle - it cannot grow indefinitely.
Early Termination: If we reach 1, we can stop immediately (it’s happy). If we see a repeated number, we can stop (it’s not happy).
Space Optimization: Floyd’s cycle detection provides O(1) space complexity compared to O(log n) for hash set approach.