202. Happy Number

Q: What's the only cycle in base 10 squared-digit iteration?

The cycle (4, 16, 37, 58, 89, 145, 42, 20, 4). Every unhappy number eventually lands in this cycle. The proof is exhaustive over residue classes mod 9.

easyAsked at Intel

A 'happy number' converges to 1 under repeated digit-square-sum iteration. Intel asks because the optimal O(1)-space solution is Floyd's cycle detection applied to a function — not a linked list — proving you can spot the cycle-detection pattern even when the structure isn't a pointer chain.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Intel loops.

Glassdoor (2026-Q1)— Intel SWE phone-screen reports cite happy-number as a recurring Floyd's-variant ask.
GeeksforGeeks (2025-09)— Intel Interview Experience archives reference happy-number with the cycle-detection follow-up.
LeetCode discuss (2025-11)— Intel-tagged in the LC company-frequency listing.

Problem

Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.

Constraints

1 <= n <= 2^31 - 1

Examples

Example 1

Input

n = 19

Output

true

Explanation: 1^2 + 9^2 = 82; 8^2 + 2^2 = 68; 6^2 + 8^2 = 100; 1^2 + 0^2 + 0^2 = 1.

Example 2

Input

n = 2

Output

false

Approaches

1. Hash set (brute)

Track every seen number. If you see n become 1, return true. If you see a value you've seen before, you're in a cycle — return false.

Time: O(log n) per step, bounded number of distinct values reached
Space: O(k) where k = unique values seen

function isHappySet(n) {
  function digitSquareSum(x) {
    let s = 0;
    while (x > 0) {
      const d = x % 10;
      s += d * d;
      x = Math.floor(x / 10);
    }
    return s;
  }
  const seen = new Set();
  while (n !== 1 && !seen.has(n)) {
    seen.add(n);
    n = digitSquareSum(n);
  }
  return n === 1;
}

Tradeoff: Works and easy to reason about. Uses O(k) extra space. The cycle-detection version achieves O(1) space.

2. Floyd's cycle detection (optimal)

Treat digit-square-sum as a function f. Walk slow at speed 1, fast at speed 2. If they meet at 1, happy. If they meet anywhere else, cycle.

Time: O(log n) per step, bounded total steps
Space: O(1)

function isHappy(n) {
  function next(x) {
    let s = 0;
    while (x > 0) {
      const d = x % 10;
      s += d * d;
      x = Math.floor(x / 10);
    }
    return s;
  }
  let slow = n;
  let fast = next(n);
  while (fast !== 1 && slow !== fast) {
    slow = next(slow);
    fast = next(next(fast));
  }
  return fast === 1;
}

Tradeoff: Constant space. The non-obvious insight: any starting n eventually enters a cycle (because digit-square-sum is bounded — for 9-digit input, max sum is 9 * 81 = 729 < input for inputs >= 1000, so the sequence stays bounded). That guaranteed cycle property is what makes Floyd's work.

Intel-specific tips

Intel reviewers want the bounded-iteration argument: 'For any n with d digits, the digit-square-sum is at most d * 81. So the sequence is bounded by max(n, 729) after the first step. A bounded integer sequence must repeat — that's the cycle Floyd's detects.' That preamble shows you've proved the algorithm terminates, not just hoped. The reduction from 'function iteration' to 'linked list cycle' is the Intel-flavored abstraction signal.

Common mistakes

Initializing fast = n instead of fast = next(n) — they'd start equal and the loop would exit immediately on the first iteration (slow !== fast is false at start).
Forgetting to check fast === 1 as the success condition — using slow alone misses the case where fast reaches 1 first.
Looping with hash set but storing the full sequence array — O(k) space but with bigger constant; Set is faster on contains.
Computing digit-square-sum by string split/map — works but allocates; the mod/div loop is constant space.

Follow-up questions

An interviewer at Intel may pivot to one of these next:

Linked List Cycle II (LC 142) — same Floyd's mechanics, on an actual linked list.
Find the Duplicate Number (LC 287) — Floyd's on array indices.
What if 'happy' is defined with sum of CUBES instead of squares? (Different basin set; same algorithm works.)
Generalize: for which bases b > 1 does every n converge to a fixed-point under digit-power-sum? (Open research in some cases; base 10 + squares is well-studied — Wikipedia lists the cycles.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why must the sequence eventually cycle (or hit 1)?

For n with d digits, n < 10^d but digit-square-sum <= d * 81. For d >= 4, 81d < 10^(d-1), so values shrink until they fit in 3 digits. Within the bounded range [1, 999], the sequence is over a finite set, so it must repeat. That repetition is the cycle Floyd's detects.

What's the only cycle in base 10 squared-digit iteration?

The cycle (4, 16, 37, 58, 89, 145, 42, 20, 4). Every unhappy number eventually lands in this cycle. The proof is exhaustive over residue classes mod 9.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Happy Number and other Intel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →