Happy Number

Difficulty: Easy | Acceptance: 59.60% | Paid: No Topics: Hash Table, Math, Two Pointers

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, and 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 numbers.

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

• Examples
• Constraints
• Hash Set Approach
• Floyd’s Cycle Detection (Two Pointers)
• Mathematical Approach

Examples

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³¹ - 1

Hash Set Approach

Intuition Use a hash set to track visited numbers. If we encounter a number we’ve seen before, we’re in a cycle and the number is not happy.

Steps

• Initialize an empty hash set to store seen numbers
• While n is not 1 and n is not in the set:
  • Add n to the set
  • Replace n with the sum of squares of its digits
• Return true if n equals 1, false otherwise

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

Complexity

• Time: O(log n) - Each iteration reduces the number significantly, and we have at most O(log n) iterations
• Space: O(log n) - In the worst case, we store O(log n) numbers in the set
• Notes: Simple and intuitive approach, but uses extra space for the hash set

Floyd’s Cycle Detection (Two Pointers)

Intuition Use Floyd’s cycle detection algorithm (tortoise and hare) to detect cycles without extra space. The slow pointer moves one step at a time, while the fast pointer moves two steps.

Steps

• Initialize slow pointer to n and fast pointer to the next value of n
• While fast is not 1 and slow is not equal to fast:
  • Move slow one step (sum of squares of digits)
  • Move fast two steps (sum of squares of digits twice)
• Return true if fast equals 1, false otherwise

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

Complexity

• Time: O(log n) - Each iteration reduces the number, and cycle detection happens in O(log n) steps
• Space: O(1) - Only uses two pointers, no additional data structures
• Notes: Optimal space complexity, elegant cycle detection without extra memory

Mathematical Approach

Intuition All unhappy numbers eventually reach 4 in their sequence. This is a proven mathematical property, so we only need to check if we reach 1 or 4.

Steps

• While n is not 1 and n is not 4:
  • Replace n with the sum of squares of its digits
• Return true if n equals 1, false otherwise

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
        
        while n != 1 and n != 4:
            n = get_next(n)
        return n == 1

Complexity

• Time: O(log n) - Each iteration reduces the number, and we terminate at either 1 or 4
• Space: O(1) - Only uses constant extra space
• Notes: Most space-efficient approach, relies on mathematical property that all unhappy numbers reach 4