Skip to main content

27. Happy Number

easyAsked at Ola

Determine whether iteratively replacing a number with the sum of squares of its digits eventually reaches 1.

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

Problem

Write an algorithm to determine if a number n is happy. Replace the number by the sum of the squares of its digits and repeat. n is happy if the process ends at 1; numbers that loop endlessly without reaching 1 are not happy.

Constraints

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

Examples

Example 1

Input
n = 19
Output
true

Example 2

Input
n = 2
Output
false

Approaches

1. Hash seen

Record every value; if you see a repeat without hitting 1, it loops.

Time
O(log n)
Space
O(log n)
const seen = new Set();
while (n !== 1 && !seen.has(n)) {
  seen.add(n);
  n = String(n).split('').reduce((s,d)=>s+d*d,0);
}
return n === 1;

Tradeoff:

2. Floyd's cycle detect

Two pointers: slow steps once, fast steps twice. They meet at 1 or in a cycle. O(1) space.

Time
O(log n)
Space
O(1)
function isHappy(n) {
  const step = x => String(x).split('').reduce((s,d)=>s+d*d,0);
  let slow = n, fast = step(n);
  while (fast !== 1 && slow !== fast) {
    slow = step(slow);
    fast = step(step(fast));
  }
  return fast === 1;
}

Tradeoff:

Ola-specific tips

Ola asks Floyd's variant to test that you can recognize cycle-detection in surprising places, like an infinite retry loop in a dispatch state machine.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →