Happy Number

A happy number is defined by the following process: starting with a positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number becomes 1, or it loops forever in a cycle that does not include 1.

Return true if the number is happy.

Why this is worth learning

Repeated digit-squaring forms a deterministic functional graph. A visited set or two-speed traversal detects whether its path reaches 1 or enters another cycle.

Before coding: one-minute experiment

What are the first successors of 19 until 1 is reached?

Function signature

func IsHappy(n int) bool

Inputs / outputs

• n: positive integer.
• Return: true if n is happy, else false.

Example

n = 19
Output: true

19 -> 82 -> 68 -> 100 -> 1

Constraints

• 1 <= n <= 2_000_000_000

Core idea (near-solution)

The sequence eventually enters a cycle. Use cycle detection (fast/slow pointers) to determine if it reaches 1.

Invariant: if there is a cycle not containing 1, fast and slow pointers will meet.

Algorithm (step-by-step)

1. Define a helper next(x) that returns the sum of squares of digits.
2. Initialize slow = n, fast = next(n).
3. While fast != 1 and slow != fast:
   • slow = next(slow)
   • fast = next(next(fast))
4. Return fast == 1.

Correctness sketch

Every state has exactly one successor: the sum of its squared decimal digits. For the stated input bound, the first successor is at most 10*81=810, and subsequent states remain in a finite range. Thus the sequence must eventually repeat or reach 1. The slow pointer advances once and the fast pointer twice; once both are in a cycle, their relative position advances by one modulo the cycle length, so they eventually meet. If fast reaches 1, repeated successors stay 1 and the number is happy. If the pointers meet away from 1, determinism traps the sequence in that non-1 cycle, proving unhappiness.

Trace (hand walkthrough)

Example input:
n = 19
Output: true

19 -> 82 -> 68 -> 100 -> 1

Walk:
- 19 -> 1^2+9^2=82
- 82 -> 8^2+2^2=68
- 68 -> 6^2+8^2=100 -> 1 -> true

Pitfalls to avoid

• Using an infinite loop without cycle detection.
• Miscomputing the digit square sum.

Debugging lens

Use 1, a known non-1 cycle such as 2, and a large input. If using a set instead, record the whole integer state, not the multiset of its digits.

Complexity

For the bounded input domain, all states after the first transition lie in a constant-sized finite range. More generally, digit processing costs O(log n) initially plus the work through the finite tail and cycle. The supplied Floyd traversal uses O(1) auxiliary space; a visited-set alternative does not.

Implementation notes (Go)

• Use a visited set or fast/slow pointers to detect cycles.
• Implement a helper to sum squares of digits.

Reconstruction checkpoint

What are the first successors of 19 until 1 is reached?

Return to Hash Map · Module quiz