Skip to main content

202. Happy Number

easyAsked at Microsoft

Happy Number is Microsoft's favorite cycle-detection question disguised as math. The trick is recognizing the digit-square sum sequence either reaches 1 or enters a cycle — so Floyd's tortoise-and-hare applies and the space drops to O(1).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft Bing/Azure phone-screen reports list Happy Number as the canonical 15-minute warm-up with the 'now do it in O(1) space' twist.
  • Blind (2025-10)— Multiple Microsoft new-grad interview compilations include Happy Number with cycle-detection follow-up.

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 to detect cycle

Keep applying the digit-square sum. Track every number seen in a set. If you see 1, return true; if you see a repeat, return false.

Time
O(log n) per step, bounded total steps
Space
O(log n)
function isHappy(n) {
  const seen = new Set();
  while (n !== 1 && !seen.has(n)) {
    seen.add(n);
    let sum = 0;
    while (n > 0) {
      const d = n % 10;
      sum += d * d;
      n = Math.floor(n / 10);
    }
    n = sum;
  }
  return n === 1;
}

Tradeoff: Easy to write. The total number of distinct values the sequence can hit is bounded (for any 32-bit input it converges below 1000 within a few steps), so the set stays small in practice.

2. Floyd's tortoise and hare (optimal O(1))

Treat the digit-square sum as a function f. Run two pointers — slow advances one step, fast advances two. If they meet at 1, happy; if they meet elsewhere, cycle.

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

Tradeoff: Same time bound, O(1) space. Microsoft loves this answer because it shows you recognized 'this is cycle detection on a function graph' and applied the classic technique.

Microsoft-specific tips

Microsoft is grading whether you can map a number problem to a graph problem. Say out loud: 'each number maps to exactly one next number via the digit-square sum, so the sequence is a chain in a functional graph — either it ends at the fixed point 1 or it eventually revisits a value, which means cycle.' That sentence is worth more than the code.

Common mistakes

  • Hard-coding a max iteration count instead of detecting the cycle.
  • Forgetting that 1 is a fixed point — n^2 = 1 stays 1 — so the loop should check equality to 1 every iteration.
  • In Floyd's, advancing slow and fast in the wrong order — slow should take one step, fast should take two, every loop iteration.

Follow-up questions

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

  • Linked List Cycle (LC 141) — same Floyd's pattern on real linked lists.
  • Find the Duplicate Number (LC 287) — Floyd's again on an index-mapping function.
  • Loop the equation backward: what numbers reach 1 in exactly k steps?

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 is this not infinite for non-happy numbers?

The digit-square sum of any 32-bit integer is bounded above by 9^2 * 10 = 810 after one step, so the sequence quickly enters a small range and must cycle by the pigeonhole principle.

Set or Floyd's?

Microsoft will accept set first. If there's time, they ask for O(1) space — that's when you reach for Floyd's. Have both ready.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →