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

More Math practice problems

See all Math problems →