#202 Happy Number
the problem
In plain words
Start from a positive int n and keep replacing it with the sum of the squares of its digits. If this ever reaches 1, n is happy. If it loops forever without reaching 1, it isn't. Return whether n is happy.
in n = 19
out true
1² + 9² = 82 → 8² + 2² = 68 → 6² + 8² = 100 → 1² + 0² + 0² = 1.
in n = 2
out false
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → … a loop without 1.
- 1 ≤ n ≤ 2³¹ − 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternFast & slow pointersHash lookup (seen before?)Digit peeling (% 10 and / 10)
After one step any int is at most 10 × 9² = 810, so the values are trapped in a small range and must eventually repeat. The sequence is a linked list that may have a cycle — detect it with a HashSet, or with Floyd's slow and fast pointers.
solutions
From brute force to optimal
Walk the sequence; stop at 1 (happy) or at a value seen before (a loop).
- seen = new HashSet<>().
- While n != 1 and seen.add(n) is true: n = next(n).
- Return n == 1.
The first step reads ~log₁₀ n digits; after it every value is ≤ 810, so the rest of the walk is bounded by a constant.
Bounded, not zero: besides n the set only ever holds values ≤ 810.
class Solution { public boolean isHappy(int n) { Set<Integer> seen = new HashSet<>(); while (n != 1 && seen.add(n)) n = next(n); // add() returns false when n was already seen: a loop return n == 1; } private static int next(int n) { int sum = 0; for (; n > 0; n /= 10) sum += (n % 10) * (n % 10); return sum; }}Treat next() as the "next node". slow moves one step, fast two; in a loop fast catches slow.
- slow = n, fast = next(n).
- While fast != 1 and slow != fast: slow = next(slow), fast = next(next(fast)).
- Return fast == 1.
Same walk as the set version, at most about three times the steps.
Two ints — no set at all.
class Solution { public boolean isHappy(int n) { int slow = n, fast = next(n); while (fast != 1 && slow != fast) { // Floyd: fast gains one step per round, so it meets slow in a loop slow = next(slow); fast = next(next(fast)); } return fast == 1; } private static int next(int n) { int sum = 0; for (; n > 0; n /= 10) sum += (n % 10) * (n % 10); return sum; }}in the room
How to say it in the interview
talk track
- First argue that the loop can't run forever on ever-bigger numbers (810 bound). That is the real question.
- Give the HashSet version, then upgrade to Floyd for O(1) space — the same trick as Linked List Cycle.
traps
- Looping
while (n != 1)without loop detection — unhappy numbers run forever. - Squaring with
Math.pow(returns a double) instead ofd * d.
what they ask next
Follow-ups
A pure math shortcut?
Every unhappy number enters the 8-number loop that contains 4, so while (n != 1 && n != 4) n = next(n); works — but explain the cycle argument first.
before you submit
Edge cases to test
- n = 1 → true at once
- Unhappy numbers fall into the loop 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
- Integer.MAX_VALUE → 260 after one step (no overflow: the maximum is 10 × 81 = 810)
practise next
Similar problems
- #141Linked List CycleEasyin Linked Lists
- #7Reverse IntegerMediumin Math & Numbers