AlgoMaster Logo

Happy Number

Last Updated: March 29, 2026

easy
3 min read

Understanding the Problem

The core idea is straightforward: take a number, sum the squares of its digits, and repeat. If you eventually hit 1, the number is happy. If you never hit 1, the process will cycle forever, and the number is unhappy.

The tricky part is the second case. How do you know when to stop if the number is NOT happy? You can't just run the process forever. The key observation is that unhappy numbers always enter a cycle. The digit-square-sum of any number below 2^31 quickly shrinks to a small range (the maximum digit-square-sum of a 10-digit number is 9^2 * 10 = 810), so the values are bounded and must eventually repeat. Once a value repeats, you're stuck in an infinite loop.

So the problem reduces to: detect whether the sequence reaches 1 or enters a cycle. This is a classic cycle detection problem.

Key Constraints:

  • 1 <= n <= 2^31 - 1 → The input can be any positive 32-bit integer. But after one iteration of digit-square-sum, even the largest 10-digit number (2,147,483,647) maps to at most 9^2 * 10 = 810. So the sequence quickly enters the range [1, 810], and cycle detection is efficient.

Approach 1: Hash Set

Intuition

The most natural way to detect a cycle: remember every number you've seen. If the current number is 1, it's happy. If the current number has appeared before, you're stuck in a cycle and it's not happy.

This is the same idea behind detecting cycles in a linked list with a visited set, or detecting infinite loops in any iterative process. You trade space for a simple termination condition.

Algorithm

  1. Create a hash set seen to store numbers we've encountered.
  2. While n is not 1 and n is not in seen:
    • Add n to seen.
    • Replace n with the sum of the squares of its digits.
  3. Return true if n equals 1, false otherwise.

Example Walkthrough

1Start: n=19, seen={}, compute 1² + 9² = 82
19
:
true
1/5

Code

We detect cycles correctly, but the hash set uses extra memory. Is there a way to detect cycles without storing every visited value?

Approach 2: Floyd's Cycle Detection (Two Pointers)

Intuition

This is the same insight behind detecting a cycle in a linked list. Instead of storing every number we've seen, we use two pointers: a slow pointer that advances one step at a time, and a fast pointer that advances two steps at a time. If there's a cycle, the fast pointer will eventually catch up to the slow pointer. If the sequence reaches 1, the fast pointer will hit 1 first.

Think of it like two runners on a track. If the track is circular, the faster runner will eventually lap the slower one. If the track has an endpoint (reaching 1), the faster runner gets there first.

Algorithm

  1. Initialize slow = n and fast = getNext(n).
  2. While fast != 1 and slow != fast:
    • Move slow one step: slow = getNext(slow).
    • Move fast two steps: fast = getNext(getNext(fast)).
  3. Return true if fast == 1, false otherwise.

Example Walkthrough

1Initialize: slow=19, fast=getNext(19)=82
slow
19
82
fast
68
100
1
1/4

Code

Both approaches iterate through the sequence, but there's an even simpler observation: every unhappy number eventually reaches the cycle containing 4.

Approach 3: Math (Hardcoded Cycle Detection)

Intuition

Every unhappy number eventually reaches the cycle 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4. This is the only cycle that exists for this process.

So instead of tracking all visited numbers or running two pointers, we can simply iterate and check: did we reach 1, or did we reach 4? If either happens, we have our answer. This is the simplest code of all three approaches, though it relies on domain-specific knowledge rather than a general algorithm.

Algorithm

  1. While n is not 1 and n is not 4:
    • Replace n with the sum of the squares of its digits.
  2. Return true if n equals 1, false otherwise.

Example Walkthrough

1n=19: not 1, not 4. Compute 1² + 9² = 82
19
n
82
68
100
1
1/5

Code