AlgoMaster Logo

Happy Number

easyFrequency6 min readUpdated June 23, 2026

Understanding the Problem

Take a number, sum the squares of its digits, and repeat. If the process reaches 1, the number is happy. If it never reaches 1, the process cycles forever, and the number is unhappy.

The second case is the harder one. How do you stop if the number is not happy? You cannot run the process forever. Unhappy numbers always enter a cycle, and the reason is that the values stay bounded. The digit-square-sum of any number below 2^31 falls into a small range (the maximum for a 10-digit number is 9^2 * 10 = 810), so the sequence can only take finitely many values. By the pigeonhole principle, some value must repeat, which means the process is in an infinite loop.

The problem reduces to detecting whether the sequence reaches 1 or enters a cycle.

Key Constraints:

  • 1 <= n <= 2^31 - 1. The input can be any positive 32-bit integer. After one iteration of digit-square-sum, even the largest value (2,147,483,647) maps to at most 810. From there the sequence stays inside the range [1, 810], so the number of distinct values, and therefore the work to detect a cycle, is bounded by a constant.

Approach 1: Hash Set

Intuition

Store every number the process produces. If the current number is 1, the number is happy. If the current number has appeared before, the sequence is in a cycle and the number is unhappy.

This is the same technique used to detect a cycle in a linked list with a visited set. It trades memory for a straightforward termination condition: the loop stops the first time a value repeats.

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

This detects cycles correctly, but the hash set grows with the number of distinct values. The next approach detects the same cycle using two pointers and constant extra space.

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

Intuition

Instead of storing every number, use two pointers over the same sequence: a slow pointer that advances one step at a time, and a fast pointer that advances two steps at a time. If the sequence contains a cycle, the fast pointer eventually laps the slow pointer and they meet. If the sequence reaches 1, the fast pointer reaches 1 first, since 1 maps to itself.

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 detect a cycle without knowing where it is. For this specific problem, the cycle is always the same one, which leads to a shorter solution.

Approach 3: Math (Hardcoded Cycle Detection)

Intuition

Every unhappy number eventually reaches the cycle 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4. For numbers in the range [1, 810] this can be verified by direct enumeration, and since every input drops into that range after one step, it covers all 32-bit inputs. This is the only cycle the process can enter.

Because 4 lies on that cycle, reaching 4 is equivalent to entering the cycle. So the loop only needs to check two stopping conditions: did the value reach 1, or did it reach 4? Reaching 1 means happy, reaching 4 means unhappy. This removes the hash set and the second pointer, at the cost of relying on a fact specific to this problem rather than a general cycle-detection 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