Code Implementation

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(number):
            total_sum = 0
            while number > 0:
                digit = number % 10
                total_sum += digit * digit
                number //= 10
            return total_sum
        
        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = get_next(n)
        return n == 1
      

class Solution {
public:
    bool isHappy(int n) {
        auto get_next = [](int number) {
            int total_sum = 0;
            while (number > 0) {
                int digit = number % 10;
                total_sum += digit * digit;
                number /= 10;
            }
            return total_sum;
        };
        std::unordered_set<int> seen;
        while (n != 1 && seen.find(n) == seen.end()) {
            seen.insert(n);
            n = get_next(n);
        }
        return n == 1;
    }
};
      

import java.util.HashSet;
class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
    private int getNext(int number) {
        int totalSum = 0;
        while (number > 0) {
            int digit = number % 10;
            totalSum += digit * digit;
            number /= 10;
        }
        return totalSum;
    }
}
      

var isHappy = function(n) {
    const getNext = (number) => {
        let totalSum = 0;
        while (number > 0) {
            let digit = number % 10;
            totalSum += digit * digit;
            number = Math.floor(number / 10);
        }
        return totalSum;
    };
    const seen = new Set();
    while (n !== 1 && !seen.has(n)) {
        seen.add(n);
        n = getNext(n);
    }
    return n === 1;
};
      

Problem Description

The "Happy Number" problem asks you to determine if a given positive integer n is a "happy number." A happy number is defined as follows:

• Start with any positive integer n.
• 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 that does not include 1.
• If the process ends in 1, the number is "happy." Otherwise, it is "unhappy."

The function should return true if n is a happy number, and false otherwise.

Thought Process

To solve the Happy Number problem, we need to simulate the process described and determine if it ends at 1 or falls into a cycle. The naive approach is to keep applying the digit-squaring process until we either reach 1 or notice that we are repeating numbers (which means we are in a loop).

The key challenge is cycle detection. If we don't keep track of previously seen numbers, we might loop forever. By storing numbers we've already computed, we can detect cycles efficiently.

This is similar to the "tortoise and hare" approach for cycle detection in linked lists, but using a set (hash table) is simpler and just as effective here.

Solution Approach

Here’s how we can solve the problem step by step:

1. Initialize a set: Create an empty set to keep track of numbers we've already seen during the process.
2. Iterate: While the current number is not 1 and hasn't been seen before, add it to the set.
3. Transform: Replace the current number by the sum of the squares of its digits. For example, if the number is 19, its digits are 1 and 9, so the next number is 1^2 + 9^2 = 82.
4. Cycle detection: If you see a number that’s already in the set, there is a cycle, and the number is not happy.
5. Termination: If you reach 1, return true; otherwise, return false.

We use a set for fast O(1) lookups to track previously seen numbers and prevent infinite loops.

Example Walkthrough

Let's walk through an example with n = 19:

1. Start with 19. Digits: 1 and 9.
   Sum of squares: 1^2 + 9^2 = 1 + 81 = 82
2. Next, 82. Digits: 8 and 2.
   Sum: 8^2 + 2^2 = 64 + 4 = 68
3. Next, 68. Digits: 6 and 8.
   Sum: 6^2 + 8^2 = 36 + 64 = 100
4. Next, 100. Digits: 1, 0, 0.
   Sum: 1^2 + 0^2 + 0^2 = 1 + 0 + 0 = 1
5. We reached 1! So, 19 is a happy number.

If at any point we got a number we had already seen, we would stop and return false because that means we are in a cycle.

Time and Space Complexity

• Brute-force approach: If we just kept transforming numbers without storing them, we could loop forever for unhappy numbers. This is not practical.
• Optimized approach (using a set):
  • Time Complexity: O(log n) per transformation (since extracting digits is proportional to the number of digits), and in practice, the sequence quickly falls into a small cycle or reaches 1. So the total number of steps is bounded and small for all practical inputs.
  • Space Complexity: O(number of unique numbers seen). For happy numbers, this is small. For unhappy numbers, there is a known small cycle (for base 10), so the space used is also small.

Summary

The Happy Number problem is a classic example of cycle detection in iterative processes. By tracking previously seen numbers with a set, we efficiently avoid infinite loops and determine whether a number is happy. The approach is simple, elegant, and leverages hash-based lookups for performance. The key insight is to recognize that the process will always fall into a cycle or reach 1, making the set-based solution both effective and easy to implement.