Happy Number

Problem in Plain English

Repeatedly replace n with the sum of the squares of its digits, returning true if the chain reaches 1 and false if it falls into a repeating cycle.

Problem Statement

Decide whether a positive integer n is a happy number. Repeatedly replace the number by the sum of the squares of its decimal digits.

Return true if the sequence reaches 1. Return false if it repeats indefinitely without reaching 1. Since the successor of 1 is again 1, reaching that value is enough to finish.

Constraints

$1 \le n \le 2^{31}-1$

Examples

Example 1

Input: n = 19
Output: true

The successors are $1^2+9^2=82$ , $8^2+2^2=68$ , $6^2+8^2=100$ , and $1^2+0^2+0^2=1$ . Reaching 1 makes the answer true.

Example 2

Input: n = 1
Output: true

The initial value already equals 1; no transformation is needed. Its successor is also 1.

Example 3

Input: n = 2
Output: false

The chain visits 2, 4, 16, 37, 58, 89, 145, 42, 20, then 4 again. A repeated 4 repeats the same successors forever without reaching 1.

Intuition

The digit-square rule gives each number exactly one successor. For Example 1, the chain is 19 to 82 to 68 to 100 to 1. A repeated value would force every later successor to repeat too, so the real task is detecting a cycle. Since a permitted input has at most ten digits, its first successor is at most 810; every later successor is at most 243. This finite range guarantees eventual repetition, including the happy fixed point 1.

Approaches

Hash Set Cycle

Solution Details

Reveal Hash Set Cycle: intuition, complexity, and code

Intuition

Replacing a number by its digit-square sum can only produce values below a small bound, so the chain must eventually repeat a value. A hash set of seen values catches that first repeat: reaching 1 means happy, meeting a value twice means a cycle, so unhappy.

Step-by-Step Logic

Define a helper that repeatedly extracts the last digit with remainder by 10, adds its square, and removes it with integer division. For 19 it returns 82.
Start with an empty seen set. Until the current value is 1 or has been seen, record it and compute its successor.
On Example 1, record 19, 82, 68, and 100 in turn, advancing to 82, 68, 100, and 1.
Return whether the stopping value is 1: true here; a repeated non-1 value instead returns false.

Why It Works

At the start of each iteration, seen contains exactly the earlier values of this chain. If the current value is 1, the input is happy by definition. If it is already in seen, the deterministic successor rule repeats the same suffix forever; because no earlier value was 1, that cycle is unhappy. Otherwise record the current value and advance to its correct successor. The finite bounded range after the first transformation ensures one of these stopping conditions eventually occurs.

Dry Run

Hash Set Cycle: variable states at each step
`n`	In `seen`?	Action	`seen` after	Next `n`
`19`	no	add `19`	`{19}`	`82`
`82`	no	add `82`	`{19, 82}`	`68`
`68`	no	add `68`	`{19, 82, 68}`	`100`
`100`	no	add `100`	`{19, 82, 68, 100}`	`1`
`1`	-	equals `1`, return `true`	`{19, 82, 68, 100}`	-

Complexity Analysis

Time Complexity

O(\log n)

Space Complexity

O(1)

The first digit extraction costs O(log n) time (with constant work for n = 1). Under the stated 32-bit domain, its successor is at most 810 and subsequent values at most 243; at most 811 distinct states including the starting value can enter the set, so the remaining time and allocated set storage are bounded constants. O(log n) is a digit-scan bound within this domain, not an arbitrary-precision claim; treating the entire fixed 32-bit domain as constant gives O(1) time too. Hash-set operations use expected constant time.

Code

Solution.java

1import java.util.HashSet;2import java.util.Set;3
4class Solution {5    public boolean isHappy(int n) {6        Set<Integer> seen = new HashSet<>();7        // Repeating a state repeats its entire future; stop before revisiting it.8        while (n != 1 && !seen.contains(n)) {9            seen.add(n);10            n = digitSquareSum(n);11        }12        return n == 1;13    }14
15    private int digitSquareSum(int n) {16        int sum = 0;17        while (n > 0) {18            int digit = n % 10;19            sum += digit * digit;20            n /= 10;21        }22        return sum;23    }24}

Hints

Hint 1

Write out where 19 goes (19 to 82 to 68 to 100 to 1) and where 2 goes. What separates the two chains?

Hint 2

Treat each value and its successor as one link in a chain: the chain either ends at 1 or repeats a value forever.

Hint 3

Store every produced value in a set to catch the first repeat, or run a slow pointer one link per round against a fast pointer moving two links and watch whether they meet or the fast one hits 1.

Edge Cases

n = 1 is already happy: both loops exit at once and return true.
n = 7 is happy through a longer chain (7 to 49 to 97 to 130 to 10 to 1), so chains are not always short.
Unhappy numbers like n = 2 never reach 1, so without cycle detection the loop runs forever.

Common Mistakes and Interview Tips

Looping until n becomes 1 with no record of seen values, which hangs forever on unhappy inputs such as 2.
Advancing the fast pointer by one step instead of two in the Floyd version, so a meeting no longer proves a cycle.
Extracting digits with plain / 10 in JavaScript, which keeps fractions; apply Math.floor after each division.
Initializing both pointers to n and testing equality before advancing would reject every input except 1. Explain the initial offset and the separate success test in an interview.

Key Takeaway

Any process mapping each value to a next value inside a bounded range must eventually repeat, so cycle tools such as seen sets and fast/slow pointers apply far beyond linked lists.