Problem Statement

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

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

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

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

Additional information

• 0 <= n <= 2^31 - 1

Example 1:

Input: n = 19
Output: true

Explanation: 1^2 + 9^2 = 82, 8^2 + 2^2 = 68, 6^2 + 8^2 = 100, 1^2 + 0^2 + 0^2 = 1. The process reaches 1, so 19 is a happy number.

Example 2:

Input: n = 2
Output: false

Explanation: The sequence 2, 4, 16, 37, 58, 89, 145, 42, 20, 4, ... enters a cycle that never reaches 1, so 2 is not a happy number.

Cycle Detection with HashSet

Intuition

This problem is essentially a Cycle Detection problem.
As we repeatedly sum the squares of the digits, one of two things will happen:

1. The sum eventually reaches 1 (Happy).
2. The sum reaches a number we have seen before, meaning we are in an infinite loop (Not Happy).

To detect this loop efficiently, we can use a HashSet.

1. The Process:

• Take the current number n.
• Calculate the sum of the squares of its digits (e.g., 19 -> 1^2 + 9^2 = 82).
• Check if this new sum is 1. If yes, return True.
• Check if this new sum is already in our seen set. If yes, we are in a loop -> return False.
• Add the sum to the seen set and repeat.

Algorithm

Step 1: Initialize an empty set visit to keep track of numbers we have encountered.

Step 2: Start a while loop that continues as long as n is not in visit.

Step 3: Inside the loop, add n to visit.

Step 4: Calculate the sum of squares of digits:

• Convert n to string, iterate, square, and sum? Or use modulo % 10 math? Math is faster.
• Example: n = 19. 1^2 + 9^2 = 82. n becomes 82.

Step 5: Check if the new n is 1. If yes, return True.

Step 6: If the loop finishes (meaning we found a duplicate n), return False.

def is_happy(n: int) -> bool:
    visit = set()
    
    while n not in visit:
        visit.add(n)
        
        # Calculate sum of squares of digits
        sq_sum = 0
        while n > 0:
            digit = n % 10
            sq_sum += digit * digit
            n //= 10
        n = sq_sum
        
        if n == 1:
            return True
            
    return False

Time & Space Complexity

• Time Complexity: O(log n). Finding the next number involves processing each digit, which takes logarithmic time relative to the value of n. The cycle length for non-happy numbers is relatively small (bounded).
• Space Complexity: O(log n). We store the numbers in the set.