Leetcode - Happy Number Solution

The Happy Number problem asks whether repeatedly squaring and summing a number's digits eventually reaches 1. If the sequence repeats a value without reaching 1, the number is not happy.

My first solution used a Set to track seen numbers. The fast and slow pointer version uses the same cycle idea with O(1) extra space.

The sequence

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 is not happy.

My first version stored each value in a Set. It stopped at 1 or a value that was already in the set:

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 detects both outcomes, but the set grows with the sequence.

Detecting a cycle

The sequence has the same shape as a linked list: each number points to the next result of sumOfSquares. A happy sequence reaches 1. Any other sequence eventually enters a cycle, so fast and slow pointers can distinguish the two cases without storing every value.

The implementation starts fast one step ahead:

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;
}

For n = 19, the pointers move as follows:

• 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 the function returns true.

If the sequence has a cycle, slow and fast eventually meet inside it. If the sequence reaches 1, the loop stops with fast === 1. The pointer variables keep the extra space at O(1), instead of the O(n) set used by the baseline.

I did not expect to use a cycle detection algorithm for this number theory problem. Each call to sumOfSquares processes the digits of its input, and the pointer loop uses constant extra storage.

The reusable idea is to treat a computed sequence as a chain of nodes. Once the next value is deterministic, fast and slow pointers can detect a cycle without a visited set.