202. Happy Number

At a Glance

• Topic: math-geometry
• Pattern: Cycle detection (Fast & Slow Pointers); digit simulation
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Bloomberg, Apple
• Frequency: High
• LeetCode: 202

Problem (one-liner)

Given a positive integer value, repeatedly replace it by the sum of the squares of its digits until the process reaches 1 (happy) or enters a cycle that never hits 1 (not happy). Return whether it is a happy number.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• "Sum of the squares of its digits"
• "Eventually equals 1" vs "loops endlessly"
• Implicit linked-list / successor graph on integers

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — O(?) unbounded — simulate with a set of seen sums; may grow large.
• Better — hash set of visited sums — O(log n) per step typical — stop on repeat.
• Optimal — Floyd cycle detection on the successor function — O(log n) time per phase / O(1) space — treat slow/fast digit-sum as linked list cycle.

Optimal Solution

Go

package main

func isHappy(value int) bool {
	slow := value
	fast := nextDigitSquareSum(value)
	for fast != slow && fast != 1 {
		slow = nextDigitSquareSum(slow)
		fast = nextDigitSquareSum(nextDigitSquareSum(fast))
	}
	return fast == 1
}

func nextDigitSquareSum(value int) int {
	sum := 0
	for value > 0 {
		digit := value % 10
		sum += digit * digit
		value /= 10
	}
	return sum
}

JavaScript

function isHappy(value) {
	let slow = value;
	let fast = nextDigitSquareSum(value);
	while (fast !== slow && fast !== 1) {
		slow = nextDigitSquareSum(slow);
		fast = nextDigitSquareSum(nextDigitSquareSum(fast));
	}
	return fast === 1;
}

function nextDigitSquareSum(value) {
	let sum = 0;
	while (value > 0) {
		const digit = value % 10;
		sum += digit * digit;
		value = Math.floor(value / 10);
	}
	return sum;
}

Walkthrough

Input: value = 19

Invariant: Floyd detects any cycle; if 1 is reached, fast == 1 and we return true.

Edge Cases

• n = 1 → true immediately
• Powers of 10 style numbers that reduce quickly
• Classic unhappy seed 4 cycles without hitting 1

Pitfalls

• Infinite loop without cycle detection or visited set
• Integer overflow (not an issue for digit-square sums on 32-bit inputs)

Similar Problems

• 009. Palindrome Number — digit-wise transformation of integers.
• 050. Pow(x, n) — iterative numeric transformation discipline.

Variants

• Return the length of the chain before hitting 1 or cycle.
• General base base digit-square happiness.

Mind-Map Tags

#cycle-detection #floyd #digit-sum #math-simulation #happy-number