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 Sam K., 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.

More Microsoft coding interview questions

See all Microsoft problems →

Companies that also ask Happy Number