loading

Happy Number — Step-by-Step Visualization

easyLeetCode #202Hash TableMathTwo Pointers

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.

Algorithm Pattern

Cycle Detection (Hash Set or Floyd's)

Key Idea

When we calculate the sum of squares of digits, the sequence will eventually either hit 1 or enter a loop. To detect this loop, we can use a Hash Set to store every number we encounter. If we see a number that's already in the set, we've found a cycle and the number is not happy. Alternatively, Floyd's Cycle-Finding Algorithm (slow/fast pointers) can be used to save space.

Step-by-Step Approach

  1. Initialize `visited = set()`.
  2. While `n != 1`:
  3. If `n` in `visited`, return `False` (cycle found).
  4. Add `n` to `visited`.
  5. Calculate `n = sum(digit² for digit in str(n))`.
  6. Return `True` (reached 1).

Common Gotchas

  • For 1-digit numbers, 1 and 7 are happy, the rest enter the cycle `[4, 16, 37, 58, 89, 145, 42, 20]`. No need to hardcode this if you use a set.

Related Problems

← All problems