Happy Number

1. Problem & Core Objective

Repeatedly replace a number by the sum of the squares of its digits. It is happy if this reaches 1; otherwise the process loops forever. Return whether n is happy.

19  →  1² + 9² = 82  →  68  →  100  →  1        happy
2   →  4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → …   not happy

Constraints: 1 <= n <= 2^31 − 1.

What's actually being tested: recognising that "loops forever" means there is a cycle in a functional graph, and that cycle detection is therefore the whole problem. The secondary test is whether you justify termination — the reason a cycle must appear quickly is a bounding argument, not an observation.

2. First-Principles Thought Process

Every sequence either reaches 1 or cycles

The map f(n) = sum of squares of digits is a function, so from any starting point the sequence is deterministic. A deterministic sequence over a finite state space must eventually repeat, and once it repeats it cycles forever.

So exactly two outcomes exist: reach 1 (which is a fixed point, f(1) = 1), or enter some other cycle. "Unhappy" means "enters a cycle not containing 1", which is precisely cycle detection on a linked structure — the same problem as Linked List Cycle, with f playing the role of next.

Why the state space collapses immediately

The state space looks like [1, 2^31), which is not obviously finite enough. But one application of f collapses it:

So after one step every value is below 810, and after a second step below 243. The reachable state space is contained in [1, 243] — a couple of hundred states, which is why a cycle is reached within a handful of iterations.

That bound is the termination proof. Without it, "it'll loop eventually" is a hope rather than an argument.

There is exactly one unhappy cycle

Every unhappy number funnels into the same cycle:

4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

Verified: over every starting point in 1..1000 — which every larger n reaches within two steps — the only cycle that occurs is this one, of length 8. That licenses the shortest solution of all:

while (n != 1 && n != 4) n = squareDigits(n);
return n == 1;

It's correct, it's O(1) space, and it's a magic constant. I'd write the general cycle detection and mention this — a solution that depends on a fact the interviewer has to take on faith is worse than one that doesn't, even when it's right.

Floyd versus a hash set

Both are standard. The hash set is O(k) space for k distinct values visited — bounded by 243 in practice, so effectively O(1) — and is easier to explain. Floyd's tortoise and hare is genuinely O(1) and is the answer if the follow-up asks for constant space with no appeal to the bound.

All three were verified to agree on every n from 1 to 200,000.

3. Solution Paths

Approach 1 — Hash set of seen values

public boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    while (n != 1 && seen.add(n)) n = squareDigits(n);
    return n == 1;
}

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

• Time O(log n) for the first step, then O(1) — bounded by the 243-state space · Space O(1) in practice

Counter-questions on this approach

⭐ "while (n != 1 && seen.add(n)) — what is that doing?"

Set.add returns false when the element is already present, so the loop exits on the first repeat. It combines "have I seen this?" and "record it" into one lookup.

The order matters: n != 1 must come first, so that 1 short-circuits before being added.

⭐ "Is the space really O(1)?"

The set holds at most the number of distinct values reachable, and after one step everything is below 810 and after two below 243. So it's bounded by a constant — but by a constant that comes from the bound argument, not from the algorithm.

I'd state it as O(1) and immediately give the reason, because "O(1) because it just is" is not an answer.

"What if n could be arbitrarily large — a BigInteger?"

The bound still applies after the first step: a d-digit number maps to at most 81d, which is far smaller than the number itself for any d > 2. So the sequence collapses into the same small range regardless of the starting size.

That's a satisfying property — the first step does essentially all the work.

Approach 2 — Floyd's cycle detection (optimal for space)

public boolean isHappy(int n) {
    int slow = n, fast = squareDigits(n);
    while (fast != 1 && slow != fast) {
        slow = squareDigits(slow);
        fast = squareDigits(squareDigits(fast));
    }
    return fast == 1;
}

• Time O(log n) then O(1) · Space O(1), genuinely

Counter-questions on this approach

⭐ "Why does the tortoise and hare work here when there's no linked list?"

Because f induces exactly the structure Floyd's algorithm needs: every state has exactly one successor, so the trajectory from any start is a "rho" shape — a tail leading into a cycle.

slow advances one step and fast two. If there's a cycle they must meet inside it; if fast reaches 1 first, the sequence terminated. It's Linked List Cycle with squareDigits as next (11).

⭐ "Why does the test say fast != 1 rather than checking both pointers?"

fast moves twice as quickly, so it reaches 1 first if 1 is reachable at all. Checking slow too would be harmless but redundant.

There is one subtlety: 1 is a fixed point, so once fast hits 1 it stays there — meaning slow would also eventually catch it and the slow != fast condition would fire. Testing fast == 1 afterwards distinguishes the two exit reasons correctly either way.

"Why is fast initialised to squareDigits(n) rather than n?"

So they start apart. With both at n the condition slow != fast is false immediately and the loop never runs. The same off-by-one appears in every Floyd implementation — either start them apart, or use a do-while.

"Is it actually better than the hash set?"

Only if you refuse to invoke the bound. Its space is O(1) by construction rather than by argument, which is a cleaner claim — and it's the version to reach for if the interviewer pushes on "what if the state space weren't small?"

Otherwise the hash set is easier to write and to explain.

Approach 3 — The n == 4 shortcut

public boolean isHappy(int n) {
    while (n != 1 && n != 4) n = squareDigits(n);
    return n == 1;
}

• Time O(log n) then O(1) · Space O(1)

Counter-questions on this approach

⭐ "Why is 4 sufficient?"

Because there is exactly one cycle among the unhappy numbers — 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 — so every unhappy sequence passes through 4. Verified: over every start in 1..1000, which every larger n reaches in two steps, no other cycle exists.

Any member of that cycle would work as the sentinel; 4 is just the smallest.

"Would you submit this?"

It passes, and it's the fastest of the three. But it encodes a fact the reader can't verify from the code, and if the transformation changed — cubes of digits instead of squares, say — it would silently be wrong, because the cube map has several cycles.

I'd write cycle detection and mention this as a known shortcut. Choosing the robust version and explaining why is a better signal than choosing the clever one.

"How would you find the constant yourself?"

Enumerate f over 1..1000, find the cycles, and check there's only one. That's a five-line script, and running it is more convincing than recalling the number.

4. Why the Optimal Solution Wins

All three are effectively constant-time after the first digit-sum, which is O(log n) in the input's magnitude.

Write the hash set, mention Floyd. The hash set makes the cycle-detection framing explicit; Floyd is the answer to "now do it in O(1) space" and it costs two lines to switch. Mention the n == 4 shortcut last, as a fact rather than as your solution.

5. Java Prerequisites

Digit extraction

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

n > 0 rather than n != 0 is fine here because the input is positive and f produces positive values. For possibly-negative input, % returns negative digits in Java and this would silently under-count (Reverse Integer).

Set.add as a test-and-insert

if (!seen.add(n)) { /* already present */ }
while (n != 1 && seen.add(n)) n = f(n);        // exits on the first repeat

Floyd's pointers must start apart

int slow = n, fast = f(n);                     // NOT fast = n
while (fast != 1 && slow != fast) { slow = f(slow); fast = f(f(fast)); }

Overflow is not a concern

f on a 10-digit number is at most 730, so nothing here approaches Integer.MAX_VALUE. Worth confirming rather than assuming, since d * d inside a loop is exactly where overflow usually hides.

6. Interview Communication Guide

Clarifying questions: Can n be 0 or negative (no — n >= 1, which matters because % would return negative digits)? Is 1 itself happy (yes; it's a fixed point)? Do you want O(1) space (I'll start with a hash set and switch to Floyd if so)?

The pitch

"The phrase 'loops endlessly in a cycle' is the hint. f(n) — the sum of squared digits — is a function, so every state has exactly one successor, and the trajectory from any starting point is a tail leading into a cycle. That makes this cycle detection, structurally identical to Linked List Cycle with f as next.

Before writing anything I'd justify why a cycle appears quickly, because otherwise 'it repeats eventually' is a hope. A d-digit number maps to at most 81d. For a 10-digit int that's at most 730, and a 3-digit number maps to at most 243. So after one step everything is below 810 and after two it's below 243 — the reachable state space is a couple of hundred values.

That bounds both the runtime and the memory. A HashSet of seen values is therefore O(1) space in practice, and the loop is while (n != 1 && seen.add(n)) — add returns false on a repeat, so it exits on the first cycle.

If you want O(1) space by construction rather than by that argument, it's Floyd: slow = f(slow), fast = f(f(fast)), initialised apart so the loop actually starts, and exit when they meet or fast reaches 1.

There's also a one-liner — while (n != 1 && n != 4) — which works because there's exactly one unhappy cycle, 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20, so every unhappy number hits 4. I verified that over every start in 1..1000. But I wouldn't submit it: it depends on a constant the reader can't check, and it breaks if the transformation changes — the cubes-of-digits variant has several cycles."

Edge cases to volunteer:

Name n = 4. It's the state the whole problem revolves around, and a solution that special-cases the wrong sentinel will fail on it specifically.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the length of the cycle for an unhappy number."

Detect the meeting point with Floyd, then walk one pointer around until it returns — that counts the cycle length. Here the answer is always 8, since there's only one cycle, but the general procedure doesn't need that fact.

Same O(1) space.

⭐ "What if the transformation were the sum of cubes of digits?"

The cycle structure changes completely — the cubes map has several fixed points (153, 370, 371, 407 are the famous ones) and multiple cycles. So the n == 4 shortcut is specific to squares and would be wrong.

Cycle detection is unaffected: Floyd and the hash set both work for any deterministic map, which is exactly why they're the right answers.

"What if the base weren't 10?"

The bound becomes d · (b−1)² for a d-digit number in base b, still collapsing the state space to something small. The cycle structure differs per base — base 2, for instance, makes every number happy, since the digit squares are 0 and 1 and the sum is the popcount, which strictly decreases.

Nice observation to offer: in base 2 this is Number of 1 Bits iterated to a fixed point.

"How many happy numbers are there below 1000?"

143. The first ten are 1, 7, 10, 13, 19, 23, 28, 31, 32, 44. Computable in a few lines, and worth being able to produce rather than recall.

"What if n were a BigInteger with thousands of digits?"

The first step still collapses it: a d-digit number maps to at most 81d, which for d = 10^4 is 810,000 — a 6-digit number. Two more steps and it's under 500. So the algorithm is unchanged; only the first digit-sum costs O(d).

This is the clean statement of why the state-space bound is the important part.

"Precompute all answers?"

After one step every value is below 810, so an 810-entry lookup table decides everything. One digit-sum plus one array read, O(log n) total with a tiny constant — the right answer if this is called in a hot loop.

"Is there a characterisation of happy numbers?"

No simple closed form. They have density around 0.15 and are believed to be infinite in both directions, but membership is decided by running the map. Saying "no known characterisation" is better than inventing one.