Happy Number

Difficulty: Easy
Topics: Hash Table, Math, Two Pointers
Link: https://leetcode.com/problems/happy-number/

Problem Description

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.

Return true if n is a happy number, and false if not.

Example 1:


Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2:


Input: n = 2
Output: false

Constraints:

1 <= n <= 231 - 1

Solution

1. Problem Deconstruction

Technical Reformulation
Given integer n ∈ [1, 2³¹-1], define transformation f(x) = Σ(digit²). Determine if sequence {n, f(n), f(f(n)), …} converges to fixed point 1 or enters cycle excluding 1. Formally: ∃k ∈ ℕ such that fᵏ(n) = 1.

Beginner Reformulation
Take any number, square its digits and add them. Keep doing this. If you eventually reach 1, it’s happy. If you get stuck repeating the same numbers without reaching 1, it’s unhappy.

Mathematical Reformulation
Let dᵢ(n) be the i-th digit of n in base-10. Define f(n) = Σᵢ[dᵢ(n)]². Determine if limₖ→∞ fᵏ(n) = 1 or ∃m such that fᵐ(n) ∈ cycle where 1 ∉ cycle.

Constraint Analysis

1 ≤ n ≤ 2³¹-1 ≈ 2.1×10⁹: Maximum 10 digits → first f(n) ≤ 10×9² = 810
After first iteration, n ≤ 810 → subsequent values bounded by 3×9² = 243
Implies cycle detection needs O(243) = O(1) space complexity
Hidden edge: n=1 immediately happy, cycles like 4→16→37→58→89→145→42→20→4 exist
Performance: Must handle worst-case 243 iterations before cycle detection

2. Intuition Scaffolding

Real-World Metaphor
Like following directions in an unfamiliar city: each number is an intersection, digit-squaring gives new directions. Happy numbers find “home” (1), others wander in neighborhoods (cycles) forever.

Gaming Analogy
Character leveling system where your stats (digits) determine next level. Happy numbers reach max level (1), others get stuck in grinding loops.

Mathematical Analogy
Studying dynamical systems: f(n) defines state transitions. Fixed points and limit cycles determine system behavior. This is discrete dynamical system analysis.

Common Pitfalls

Assuming all numbers eventually reach 1 or obvious cycle
Not detecting cycles beyond immediate repetition
Handling n=1 as special case incorrectly
Infinite loops from missing cycle detection
Optimizing digit extraction prematurely
Confusing cycle detection with mere repetition checking

3. Approach Encyclopedia

Brute Force with Cycle Detection

function isHappy(n):
    seen = empty_set
    while n ≠ 1:
        if n in seen: return false
        add n to seen
        n = sum_of_squared_digits(n)
    return true

Complexity: Time O(k) where k ≤ 243, Space O(k) for seen set

Floyd’s Cycle Detection (Tortoise & Hare)

function isHappy(n):
    slow = fast = n
    while fast ≠ 1 and next(fast) ≠ 1:
        slow = next(slow)
        fast = next(next(fast))
        if slow == fast: return false
    return true

Complexity: Time O(k), Space O(1) - mathematical proof: cycle length detection in O(λ+μ) where λ=cycle length, μ=prefix length

Mathematical Optimization
Only cycles in happy number process: {4,16,37,58,89,145,42,20,4}. Hardcode this set.

function isHappy(n):
    while n ≠ 1 and n ≠ 4:
        n = sum_of_squared_digits(n)
    return n == 1

Complexity: Time O(k), Space O(1) - proof: all unhappy numbers reach cycle containing 4

Visualization
For n=19:

19 → 1²+9²=82 → 8²+2²=68 → 6²+8²=100 → 1²+0²+0²=1 ✓

For n=2:

2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 (cycle!)

4. Code Deep Dive

Optimal Solution (Cycle Detection)

def isHappy(n: int) -> bool:
    def get_next(number: int) -> int:
        total_sum = 0
        while number > 0:
            number, digit = divmod(number, 10)  # Extract rightmost digit
            total_sum += digit ** 2
        return total_sum
    
    slow_runner = n
    fast_runner = get_next(n)
    
    while fast_runner != 1 and slow_runner != fast_runner:
        slow_runner = get_next(slow_runner)           # 1 step
        fast_runner = get_next(get_next(fast_runner)) # 2 steps
    
    return fast_runner == 1

Line-by-Line Analysis

Line 2-6: get_next computes digit squares sum using Euclidean division
Line 8: slow_runner starts at n - represents single iteration steps
Line 9: fast_runner starts one step ahead - accelerates cycle detection
Line 11: Loop until fast finds 1 (happy) or meets slow (cycle)
Line 12-13: Tortoise (1x speed) vs Hare (2x speed) movement
Line 15: Only happy if fast runner reached 1

Edge Case Handling

n=1: Fast runner starts at get_next(1)=1 → immediate return True
n=2: Enters 4→16→37→… cycle, slow meets fast at 16 → return False
Large n=9999999999: First iteration reduces to 810, then bounded search

5. Complexity War Room

Hardware-Aware Analysis

243-element worst case fits in L1 cache (typical 32-64KB)
Integer operations avoid floating-point bottlenecks
Branch prediction favors early termination (most numbers decide quickly)

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute + Set	O(k)	O(k)	10/10	✅ Clear logic
Floyd Cycle	O(k)	O(1)	7/10	✅ Demonstrates CS fundamentals
Hardcoded	O(k)	O(1)	6/10	❌ Requires math insight

6. Pro Mode Extras

Variant: Happy Prime Numbers
“Find all happy numbers ≤ N that are also prime” requires combining with primality test.

Variant: K-Happy Numbers
Generalize to sum of k-th powers: fₖ(n) = Σdigitᵏ. Changes cycle structures and convergence.

Variant: Happy in Other Bases
Analyze in base-b: different digit squares lead to new fixed points and cycles.

Interview Cheat Sheet

Always mention cycle detection necessity first
Compare time/space tradeoffs explicitly
Test n=1 (immediate happy) and n=2 (canonical unhappy)
Note mathematical optimization exists but requires proof
Digit extraction: divmod vs str conversion discussion point

#202 - Happy Number