Skip to main content

202. Happy Number

easy

Decide whether repeatedly summing the squares of an integer's digits converges to 1 or enters a cycle. A cycle-detection problem disguised as a number-theory toy — a great place to practice Floyd's slow/fast pointer outside linked lists.

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

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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Iterate the digit-square-sum process. The question is: how do you detect non-convergence?

Hint 2

Option A: track every value you've seen in a hash set. If you ever revisit a value, you're in a cycle that doesn't contain 1, so return false.

Hint 3

Option B: Floyd's tortoise and hare. Advance slow one step and fast two steps per round. If they meet at a value != 1, it's a cycle.

Hint 4

There's a math shortcut: any unhappy number eventually reaches the cycle 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4. Detecting 4 is sufficient but less general.

Solution approach

Reveal approach

Write a helper squareDigitSum(n) that pops digits and accumulates the sum of their squares. Apply Floyd's cycle detection: slow = squareDigitSum(n), fast = squareDigitSum(squareDigitSum(n)). Loop: if fast == 1 return true; if slow == fast return false (non-1 cycle); otherwise step slow once and fast twice. The state space is bounded — for any n, the sum-of-digit-squares quickly drops below ~243 (3-digit numbers max out at 9^2*3=243), so the iteration is fast. O(log n) time per step with constant total iterations, O(1) space — Floyd avoids the hash set.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • cycle-detection
  • fast-slow-pointers
  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Happy Number and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →