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.

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

• Invariant: if there is a cycle not containing 1, fast and slow pointers will meet.
• The map counts/associations are updated consistently per element.
• Lookups use this exact state, so decisions are based on full prior data.
• Therefore the result is correct for the entire input.

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.

Complexity

• Time: O(k) where k is the cycle length (small).
• Extra space: O(1).

Implementation notes (Go)

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