Happy Number

Easy#202cycle

Take a positive number and replace it with the sum of the squares of its digits, again and again. The number is happy if this gets to 1, and not happy if it goes round and round without ever reaching 1. Return whether n is happy. Our example: n = 7, which goes 7 → 49 → 97 → 130 → 10 → 1 — the answer is true.

202 Happy NumberWalkthrough · 1×

Example: n = 7: each number leads to the sum of the squares of its digits, 7 → 49 → 97 → 130 → 10 → 1 → 1.

n74997130101slow
slowfastwhere they meet

slow = n = 7

01/19
restart · back · play · step
Speed
1function isHappy(n):
2 slow = n
3 fast = next(n) // the sum of squared digits
4 while slow != fast:
5 slow = next(slow)
6 fast = next(next(fast))
7 return slow == 1
state
slow
7
fast
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Each number has exactly one next number, so the numbers form a linked list, and it cannot grow forever: a number with d digits leads to at most 81·d, less than the number itself once it has four digits. So the list soon drops below a thousand, stays there and sooner or later comes back to a number it has met.
  2. So every list ends in a loop, and 1 is a loop too: next(1) = 1. Slow and fast meet on whatever loop it is, and the answer is just whether they meet on 1.
  3. No set of seen numbers is needed: the two pointers find the loop. Every number that is not happy ends in the same loop, 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4.

Complexity

Time O(log n): the first step reads the digits of n, about log n of them, and gives at most 81 per digit, under a thousand for any 32-bit n; from there the path and its loop are short. Memory O(1): two numbers.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.