Skip to main content

202. Happy Number

easy

A number is 'happy' if repeatedly summing the squares of its digits eventually reaches 1. Detect a happy number — and detect the cycle when it isn't. Either a hash set tracking visited values or Floyd's tortoise-and-hare on the digit-square function.

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

Unhappy numbers cycle — that's what makes detecting non-happy possible.

Hint 2

Hash-set approach: track every visited value. If you see a repeat, that's a cycle (return false). If you reach 1, return true.

Hint 3

Floyd's cycle detection: tortoise-and-hare on f(x) = sum of squared digits. If slow ever catches fast at 1, happy; otherwise cycle (not happy).

Solution approach

Reveal approach

Two approaches. Hash-set version: maintain a set of seen values. Loop: if n == 1 return true; if n is in seen return false; else add n to seen and n = sum_squares_of_digits(n). Where sum_squares_of_digits(x) extracts digits via x % 10 and x //= 10, squaring and summing. O(log n) per step; total work is bounded because values stay small (any 4+ digit input shrinks below 4 digits within one step). Floyd's version (O(1) extra space): slow = n, fast = next(n). While fast != 1 and fast != slow, slow = next(slow), fast = next(next(fast)). Return fast == 1. Cycle detection turns the implicit graph into a linked-list cycle problem.

Complexity

Time
O(log n) per step, bounded total
Space
O(log n) or O(1) with Floyd's

Related patterns

  • hash-set
  • cycle-detection
  • math

Related problems

Asked at

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

  • Amazon
  • Google
  • Apple
  • Airbnb

More Hash Tables practice problems

See all Hash Tables problems →