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
- 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.
- Remember what you have seen. A set
seenholds every value visited so far. Checkingn not in seenis an average O(1) lookup. - Write the loop.
while n != 1 and n not in seen:addntoseen, then replacenby the sum of the squares of its digits (str(n)gives the digits). - Read the result. The loop ends when
nis 1 (happy) or whennhas been seen (a cycle), soreturn n == 1answers both. - 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 == 1In 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
| Approach | Time | Space |
|---|---|---|
| Brute force with a step cap | O(cap · digits): the loop always runs up to the cap for unhappy numbers | O(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 − 1 | O(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.
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.
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?
The rule is deterministic, so a repeated value proves a loop and a set finds it. A fixed small number of runs may stop before the loop has appeared.
2. Why can the shown loop answer False as soon as a value repeats?
The same input always gives the same output, so a repeated value means the same steps follow again and 1 can never appear. It can return to earlier values, and the values do not grow.
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?
For 7 the variant gives 7 again and reports False, while the correct code reports True. For 19 the digit sums are 10, then 1, which accidentally gives the same True. For 2 it is False in both versions, and 1 is True in both.
Score 60% or more and the lesson is marked complete.