LeetCode 202 · Easy · Math & Geometry

Happy Number

Replace n by the sum of the squares of its digits, again and again. If this reaches 1, n is happy; if it loops forever without reaching 1, it is not.

O(log n)time per step, few steps
O(log n)space for the set
cycle detectionseen set

n: whole number from 1 to 9999

Sequence index = step number · every value goes into visit before it is squared · an arc back means a repeat

public boolean isHappy(int n) { Set<Integer> visit = new HashSet<>(); while (!visit.contains(n)) { visit.add(n); n = sumOfSquares(n); if (n == 1) { return true; } } return false;}private int sumOfSquares(int n) { int output = 0; while (n > 0) { int digit = n % 10; output += digit * digit; n = n / 10; } return output;}
n
—
next
—
visit.size()
0

Why it works

  1. Just looping is not enough: an unhappy number never reaches 1, so a plain while n != 1 runs forever. You need to notice a repeat.
  2. The values stay small, so they must repeat: a number with d digits maps to at most 81·d, so after a step or two every value is below 1000, and from then on the sequence stays below it. A sequence trapped in a finite range either hits 1 or revisits a value, and a revisit means a loop forever.
  3. A set spots the repeat: add each value before squaring; the first value already in visit closes the cycle. Every unhappy number falls into the same 8-value loop: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4.
  4. Cost: each step is O(digits) = O(log n), and only a handful of distinct values ever appear, so the set stays tiny.
  5. Pitfall: check for 1 right after computing the next value, or a happy number would need one extra round (1 maps to 1, which is then "seen" and wrongly returns false if you only test membership).
  6. Follow-up, O(1) space: Floyd's fast and slow pointers, as in Linked List Cycle: slow takes one step, fast takes two, and they meet inside the loop; happy exactly when they meet at 1.