Leetcode - Happy Number Solution

"Happy Number" sounds like a fun math puzzle, but it's actually a clever way to practice cycle detection algorithms. The problem asks: can you repeatedly square and sum a number's digits until you get 1? If you enter a cycle instead, the number isn't happy.

My first solution used a Set to track seen numbers, which worked but used O(n) space. Then I applied the fast and slow pointers technique from cycle detection, reducing the space complexity to O(1). This problem beautifully connects number theory with algorithm techniques.

The Problem

A number is "happy" if I can repeatedly:

1. Take its digits
2. Square each digit
3. Sum the squares
4. Repeat until I get 1

If I never get 1 and instead enter a cycle, it's not happy.

My First Attempt

I thought: "I'll just keep calculating until I get 1 or see a repeat." So I used a Set to track seen numbers:

function isHappyNaive(n) {
  let seen = new Set();

  while (n !== 1 && !seen.has(n)) {
    seen.add(n);
    n = sumOfSquares(n);
  }

  return n === 1;
}

function sumOfSquares(n) {
  let sum = 0;
  while (n > 0) {
    let digit = n % 10;
    sum += digit * digit;
    n = Math.floor(n / 10);
  }
  return sum;
}

This worked, but I was using O(n) space. I wondered if I could do better.

Applying Fast and Slow Pointers

Then I remembered the fast and slow pointers technique from cycle detection! The idea:

• If the number is happy, we'll eventually reach 1
• If it's not happy, we'll enter a cycle
• Fast and slow pointers can detect cycles without extra space

Here's my solution:

function isHappy(n) {
  let slow = n;
  let fast = sumOfSquares(n); // Fast starts one step ahead

  // Keep going until fast reaches 1 or slow catches up to fast
  while (fast !== 1 && slow !== fast) {
    slow = sumOfSquares(slow); // Move slow one step
    fast = sumOfSquares(sumOfSquares(fast)); // Move fast two steps
  }

  return fast === 1; // If fast reached 1, it's happy!
}

function sumOfSquares(n) {
  let sum = 0;
  while (n > 0) {
    let digit = n % 10;
    sum += digit * digit;
    n = Math.floor(n / 10);
  }
  return sum;
}

Tracing an Example

Let me trace through n = 19:

• slow = 19, fast = sumOfSquares(19) = 82
• slow = 82, fast = sumOfSquares(sumOfSquares(82)) = sumOfSquares(68) = 100
• slow = 68, fast = sumOfSquares(sumOfSquares(100)) = sumOfSquares(1) = 1
• fast === 1, so return true! 19 is happy!

Why This Works

The key insight: if there's a cycle, slow and fast will eventually meet. If there's no cycle (number is happy), fast will reach 1 first. This gives us O(1) space instead of O(n)!

What Surprised Me

I was surprised that this mathematical problem could be solved with a cycle detection technique. It showed me how techniques from one domain (linked lists) can apply to completely different problems (number theory).

Key Takeaways

• Cycle detection techniques apply beyond linked lists
• Fast and slow pointers can detect cycles in O(1) space
• The sum of squares function creates a sequence that either reaches 1 or cycles
• This problem connects number theory with algorithm techniques

This problem was a great reminder that algorithm techniques are tools that can be applied creatively to different domains. The connection between cycle detection and happy numbers still amazes me!