Happy Number

Examples

Input: n = 19
Output: true

19 -> 1²+9² = 82 -> 8²+2² = 68 -> 6²+8² = 100 -> 1²+0²+0² = 1. It reaches 1, so it's happy.

Input: n = 2
Output: false

2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 - it loops back to a number already seen (4) without ever reaching 1.

Input: n = 1
Output: true

It's already 1.

Constraints

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

Approach

The direct way to check this is to simulate the digit-squaring process step by step, keeping a set of every number produced so far. If the process ever reaches 1, the number is happy. If it ever produces a number that's already in the set, it's stuck in a loop, and the number is not happy.

There's a way to do the same check without remembering every number seen. Since the sequence of numbers this process produces either reaches 1 or falls into a repeating loop, it behaves exactly like a linked list that either ends or cycles. That means the classic "fast and slow pointer" trick works here too: keep one value that takes one step of the process at a time, and another that takes two steps at a time. If they ever land on the same number, the process is looping - the number is happy only if that shared number happens to be 1.

Solutions

Brute Force - Hash Set of Seen Values

Repeatedly replace the number with the sum of the squares of its digits, recording every value seen in a set. Stop and return true if the number becomes 1, or false if it repeats a value already seen.

function isHappy(n) {
  const seen = new Set();

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

  return n === 1;
}

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

Time: O(log n) per step to compute digit squares, over a bounded number of steps before a repeat occurs · Space: O(k), where k is the number of distinct values produced before the sequence reaches 1 or repeats

Optimal - Fast and Slow Pointers (Cycle Detection)

Advance one value ('slow') by a single step of the digit-squaring process, and another ('fast') by two steps at a time. If the sequence loops, the faster-moving value is guaranteed to eventually land on the same number as the slower one. When that happens, the original number is happy only if that shared value is 1.

function isHappy(n) {
  let slow = n;
  let fast = sumOfSquaredDigits(n);

  while (fast !== 1 && slow !== fast) {
    slow = sumOfSquaredDigits(slow);
    fast = sumOfSquaredDigits(sumOfSquaredDigits(fast));
  }

  return fast === 1;
}

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

Time: O(log n) per step, over a bounded number of steps · Space: O(1)