LeetCode 202 · Math & Geometry

Happy Number, explained with a picture

A chain of number plates that may loop.

EasyMath & Geometry
▶ Watch it step by step

The problem

Replace a number with the sum of the squares of its digits, and repeat. If you eventually reach 1, the number is happy. If it loops forever, it isn’t.

Input:  19
Output: true   (19 → 82 → 68 → 100 → 1)

Picture it

Picture a chain of number plates, each pointing to the next number. Either the chain reaches 1, or it enters a loop. We keep a set of numbers already seen; if a number shows up again, we’re in a loop and the answer is false.

How to recognise it

  • You repeat a deterministic rule on a value: the next value depends only on the current one.
  • You ask whether the sequence reaches a goal (here 1) or repeats forever.
  • In such a sequence, a value that appears twice means a loop, because the same input gives the same output.
  • The values are bounded, so the sequence must either hit the goal or revisit something.
  • This is the same idea as finding a cycle in a linked list.

Start with brute force

Apply the rule over and over and hope to reach 1. Without a way to detect a loop, you must stop at some fixed number of steps.

def happy_brute(n, cap=1000):
    for _ in range(cap):
        if n == 1:
            return True
        n = sum(int(d) ** 2 for d in str(n))
    return False

This works on every number I tried (all numbers below 20,000, plus random numbers up to 2^31 − 1), but only because the cap is generous. Time is O(cap · digits). The weakness is that the cap is a guess: a smaller cap could miss a long chain, and nothing explains why 1000 is enough. Without a cap, an unhappy number would loop forever. Space is O(1).

From brute force to the idea

  1. Make the loop certain. If a value appears a second time, the sequence will repeat the same steps forever, so it can never reach 1 later. Stop and answer False.
  2. Remember what you have seen. A set seen holds every value visited so far. Checking n not in seen is an average O(1) lookup.
  3. Write the loop. while n != 1 and n not in seen: add n to seen, then replace n by the sum of the squares of its digits (str(n) gives the digits).
  4. Read the result. The loop ends when n is 1 (happy) or when n has been seen (a cycle), so return n == 1 answers both.
  5. Why it ends quickly. A number with 10 or fewer digits turns into at most 10 × 81 = 810 after one step, so the values stay small and cannot grow without end. The unhappy numbers all fall into the loop 4, 16, 37, 58, 89, 145, 42, 20.

This is the key idea: the sequence is deterministic, so a repeated value proves a loop, and a set detects repeats.

The key idea

Detect a cycle with a set (or fast/slow pointers). Numbers shrink quickly, so it’s fast.

Python solution

def is_happy(n):
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = sum(int(d) ** 2 for d in str(n))
    return n == 1

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force with a step capO(cap · digits): the loop always runs up to the cap for unhappy numbersO(1)
Set of seen values (shown code)O(steps · digits). Steps stay small: at most 20 in my tests of every number below 100,000 and a random sample up to 2^31 − 1O(steps): the set holds each visited value once

Edge cases

  • n = 1: the loop does not start and the code returns True.
  • Happy numbers: the first few are 1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, and is_happy(19) is True through 82, 68, 100, 1.
  • Unhappy numbers (2, 4): return False when the loop 4, 16, 37, 58, 89, 145, 42, 20 repeats.
  • The largest allowed value (2^31 − 1 = 2147483647): returns False.
  • Single digits: 1 and 7 are happy; every other single digit is not.
  • Zero: is_happy(0) returns False, since 0 maps to 0 and repeats. The problem asks for n ≥ 1.

Common mistakes

  • Summing the digits instead of their squares. is_happy(7) then becomes False, because the sum of the digits of 7 is 7.
  • Having no cycle check, so unhappy numbers loop forever.
Your turn: O(1) space

Solve the same problem without a set, using two pointers like cycle detection in a linked list. Describe your approach, then write it if you like.

Compare with our answer

Move a slow value one step and a fast value two steps. If they ever meet, there is a cycle. The fast value may land on 1 first, which means happy.

def step(n):
    return sum(int(d) ** 2 for d in str(n))

def is_happy_fast(n):
    slow, fast = n, step(n)
    while fast != 1 and slow != fast:
        slow = step(slow)
        fast = step(step(fast))
    return fast == 1

It agrees with the set version for every n from 1 to 19,999 and for 2,000 random values up to 2^31 − 1. Time O(steps · digits), space O(1).

A strong answer mentions: the two speeds, stopping when fast reaches 1 or when the two meet, and that 1 is a fixed point (1 maps to 1), so a happy value is not a cycle failure.

Check what stuck

1. A rule turns every number into another number, and you must decide whether the sequence reaches 1 or loops forever. Which approach fits best?

2. Why can the shown loop answer False as soon as a value repeats?

3. A learner replaces the squares with plain digits: n = sum(int(d) for d in str(n)). For which input does the result change from the correct answer?

Score 60% or more and the lesson is marked complete.