Skip to main content

202. Happy Number

easyAsked at Goldman Sachs

A number is 'happy' if repeated sum-of-squares-of-digits eventually reaches 1; otherwise the chain enters a cycle. Goldman Sachs uses Happy Number to test cycle detection — the candidate who reaches for Floyd's tortoise-and-hare instead of a hash set earns the bonus point.

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

Source citations

Public interview reports confirming this problem appears in Goldman Sachs loops.

  • Glassdoor (2026-Q1)— Goldman Sachs SWE phone-screen reports specifically mention Happy Number as a 'cycle detection awareness' question.
  • LeetCode Discuss (2025-12)— Happy Number sits in the top-15 of LeetCode's Goldman Sachs company tag.

Problem

Write an algorithm to determine if a number n is 'happy'. A happy number is defined by the following process: start with any positive integer, replace the number by the sum of the squares of its digits, and repeat until the number equals 1 (happy) or it loops endlessly in a cycle which does not include 1. Return true if n is a happy number, otherwise false.

Constraints

  • 1 <= n <= 2^31 - 1

Examples

Example 1

Input
n = 19
Output
true

Explanation: 19 → 82 → 68 → 100 → 1.

Example 2

Input
n = 2
Output
false

Explanation: Enters the cycle 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4.

Approaches

1. Hash set cycle detection

Iterate the next-number function; if we ever see a number twice (and that number isn't 1), it's a cycle.

Time
O(log n)
Space
O(log n)
function isHappySet(n) {
  const seen = new Set();
  while (n !== 1 && !seen.has(n)) {
    seen.add(n);
    n = next(n);
  }
  return n === 1;
}

function next(n) {
  let sum = 0;
  while (n > 0) {
    const d = n % 10;
    sum += d * d;
    n = Math.floor(n / 10);
  }
  return sum;
}

Tradeoff: Clearest to write. The set bounds: after one iteration the value stays below 1000 (since each digit's square is at most 81 and 32-bit ints have at most 10 digits → 810), so the cycle is small and the set fits easily.

2. Floyd's tortoise and hare (optimal space)

Detect the cycle using two pointers — one stepping once, one stepping twice. If they meet at 1, happy; if they meet elsewhere, cycle.

Time
O(log n)
Space
O(1)
function isHappy(n) {
  let slow = n, fast = next(n);
  while (fast !== 1 && fast !== slow) {
    slow = next(slow);
    fast = next(next(fast));
  }
  return fast === 1;
}

function next(n) {
  let sum = 0;
  while (n > 0) {
    const d = n % 10;
    sum += d * d;
    n = Math.floor(n / 10);
  }
  return sum;
}

Tradeoff: O(1) extra space — the linked-list cycle-detection algorithm applied to the implicit graph 'next(n)'. Goldman interviewers love this version because it shows you recognize the connection to a classic algorithm.

Goldman Sachs-specific tips

Goldman Sachs interviewers are explicitly looking for the moment you say 'this is a cycle-detection problem on an implicit graph where the edges are the next() function'. That framing wins the question — once you say it, the choice of hash set vs Floyd is just an implementation detail. Lead with the set, then mention 'I can do it in O(1) space with Floyd' to get the bonus.

Common mistakes

  • Looping forever because you didn't realize non-happy numbers cycle (they NEVER diverge to infinity for 32-bit input).
  • Setting an arbitrary iteration cap instead of detecting the cycle — works on the test cases but is fragile.
  • Forgetting the n !== 1 check when initializing fast in Floyd's version.

Follow-up questions

An interviewer at Goldman Sachs may pivot to one of these next:

  • Prove every non-happy number enters a cycle. (Hint: max next() value is bounded.)
  • Could you do this in O(1) space WITHOUT Floyd? (Yes — use the mathematical fact that all unhappy chains pass through 4.)
  • Generalize to 'square the digits in base b' — for which bases is every number happy?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What's the smallest unhappy number?

2. 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 — and we're back to 4, so it loops forever.

Is the 'check if it ever hits 4' trick a valid answer?

Yes and Goldman will accept it if you can name why every unhappy number passes through 4. The interviewer will likely follow up with 'why?' to make sure you understand the proof, but it's the genuinely O(1)-space solution that doesn't require Floyd.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →