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 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

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

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →