A catalog job folded warehouse ids into a “stability checksum” by repeatedly replacing the id with the sum of squares of its digits, treating 1 as settled. Staging ids of a few digits returned in microseconds. A nightly dump of sequential ids entered a repeating loop of those sums — the worker was still iterating when the lock expired.

Happy Number asks whether repeatedly replacing n with the sum of squares of its digits reaches 1. Digit extraction is free. Chasing the next sum forever uses that and still never returns when the sequence cycles.

This is an interview writeup, not a hashing lecture. The hash table post owns buckets and collisions. Here we only care about remembering sums we have already seen, the same idea as Contains Duplicate: a set remembers, so a repeat is a lookup, not an unbounded chase.

The problem

Given a positive int n, replace it with the sum of the squares of its digits, again and again. Return true if you ever reach 1. Return false if the sequence repeats a value before that — you are in a cycle that never includes 1.

n = 82  →  true     82 → 68 → 100 → 1
n = 4   →  false    4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
n = 1   →  true     already 1

Note: 1 is a fixed point: the next sum is 1 again. That is success, not a cycle. Unhappy numbers share one short loop that never contains 1. The 4 walk above is that loop.

Unbounded replacement is the honest brute force

Keep replacing until you hit 1. Correct when the sequence is happy. It never returns when the sequence is not.

boolean isHappyUnbounded(int n) {
    while (n != 1) {
        int sum = 0;
        int x = n;
        while (x > 0) {
            int d = x % 10;
            sum += d * d;
            x /= 10;
        }
        n = sum;
    }
    return true;
}

At n = 82 this lucks into 1 and looks finished. At n = 4 it is still looping when the interview is over. A huge step cap is the production-shaped cousin: it returns false after giving up, which is right on the known unhappy cycle and a false negative if a happy path were longer than the cap. Neither version asked have I already seen this sum?

A set of seen sums catches the cycle

Before you compute the next sum, the set holds every value this sequence has already visited.

  • If n is already a member, you are done: return false — that is a cycle.
  • If n == 1, return true.
  • Otherwise add n, replace it with the next sum, and continue.

You never chase forever. You never need a step cap. A repeat is membership, the same collision Contains Duplicate returns on.

Walk a happy start and the unhappy cycle:

n = 82

82   seen {}              miss, not 1, add 82,  next = 68
68   seen {82}            miss, not 1, add 68,  next = 100
100  seen {82, 68}        miss, not 1, add 100, next = 1
1    seen {82, 68, 100}   n == 1, return true

n = 4

4    seen {}                         miss, not 1, add 4,   next = 16
16   seen {4}                        miss, not 1, add 16,  next = 37
37   seen {4, 16}                    miss, not 1, add 37,  next = 58
58   seen {4, 16, 37}                miss, not 1, add 58,  next = 89
89   seen {4, 16, 37, 58}            miss, not 1, add 89,  next = 145
145  seen {4, 16, 37, 58, 89}        miss, not 1, add 145, next = 42
42   seen {4, 16, 37, 58, 89, 145}   miss, not 1, add 42,  next = 20
20   seen {4, 16, 37, 58, 89, 145, 42}  miss, not 1, add 20, next = 4
4    seen {4, 16, …, 20}             hit, return false

The Java is that walk, with a small next(n) helper for the digit-square step:

boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    while (true) {
        if (seen.contains(n)) {
            return false;
        }
        if (n == 1) {
            return true;
        }
        seen.add(n);
        n = next(n);
    }
}

int next(int n) {
    int sum = 0;
    while (n > 0) {
        int d = n % 10;
        sum += d * d;
        n /= 10;
    }
    return sum;
}

Time is O(log n) — one digit pass on the original value, then a short walk of already-small sums until 1 or a repeat. Space is O(1) — the seen set of the unhappy cycle, a handful of small integers, not a table that grows with the original n.

Note: Do not treat 1 as a cycle. next(1) is 1. If you insert 1 into the set and then keep going, the next visit looks like a repeat and you return false for a number that is happy. Check for 1 before you add, or loop while (n != 1) so 1 never enters the set. The Contains Duplicate collision test (add returns false) is then safe: it only fires on the unhappy loop.

What interviewers usually poke next

  • Floyd on next(n). Slow takes one replacement, fast takes two. They always meet: 1 is a length-1 loop (next(1) is 1), and unhappy numbers share the other loop. Meeting at 1 is still happy — that fixed point is not the cycle-false the set returns. Meeting elsewhere is the unhappy cycle. O(1) extra space. Say that as a follow-up, not as the default — this path asked for a set first.
  • Already 1. Return true before any add. The empty set is not a cycle.
  • 0. next(0) is 0. The set sees 0 twice and returns false. Zero never reaches 1.
  • Contains Duplicate. Same membership test, different generator: that prompt walks an array; this one walks sums you produce. A repeat still means “stop.”

You are done with this problem when you can say, out loud, why the unbounded loop is honest when it hits 1, why it hangs on a cycle, and why the set returns false on the first repeat instead of chasing forever.