139.Happy Number

EasyMath & Geometry · 4/8

Problem

A number is happy if repeatedly replacing it with the sum of the squares of its digits eventually reaches 1. If the process instead loops forever in a cycle that never includes 1, the number is not happy.

Given a positive integer n, return true if it is a happy number and false otherwise.

Examples

Input:  n = 19
Output: true
Explanation: 1² + 9² = 82 → 8² + 2² = 68 → 6² + 8² = 100 → 1² + 0² + 0² = 1.

Input:  n = 2
Output: false
Explanation: 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ... the cycle repeats without 1.

Constraints

1 <= n <= 2^31 - 1

💡 Key Insight

The sequence can't grow without bound: any number with d digits maps to at most 81 · d, so after a step or two every value is below 1000 (any 3-digit number maps to at most 243). With finitely many values the sequence must eventually repeat — either it reaches 1 (which maps to itself) or it enters a cycle. So this is cycle detection on an implicit linked list: use a hash set, or Floyd's tortoise-and-hare in O(1) space.

Hash Set

TimeO(log n)SpaceO(log n)

Intuition

Walk the sequence and remember every value seen. If we hit 1, it is happy. If we see a value a second time, we are in a cycle that doesn't contain 1.

Algorithm

seen = {}.
While n != 1:
- If n is in seen, return false.
- Add n, set n = next(n) (sum of squared digits).
Return true.

Visualization

n = 2
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
                                            ^ 4 is already in seen → false

Code

java

import java.util.*;

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1) {
            if (!seen.add(n)) return false; // revisited: stuck in a cycle
            n = next(n);
        }
        return true;
    }

    private int next(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
}

Complexity

Time: O(log n) — the first step costs O(digits of n) = O(log n); after that values are below 243 and the number of further steps is bounded by a constant.
Space: O(log n) — the set holds the values visited, a bounded number after the first step.

Floyd's Cycle DetectionOptimal

TimeO(log n)SpaceO(1)

Intuition

Think of x → next(x) as a linked list. Move a slow pointer one step and a fast pointer two steps at a time. If the list ends at 1 (a self-loop), fast reaches 1 first. Otherwise both are trapped in a cycle and fast eventually laps slow, so they meet at a value other than 1. No memory is needed.

Algorithm

slow = n, fast = next(n).
While fast != 1 and slow != fast:
- slow = next(slow), fast = next(next(fast)).
Return fast == 1.

Visualization

flowchart LR
    A["4"] --> B["16"]
    B --> C["37"]
    C --> D["58"]
    D --> E["89"]
    E --> F["145"]
    F --> G["42"]
    G --> H["20"]
    H --> A
    S["2"] --> A

n = 2, cycle of length 8 shown above (1 is never reached)

step   slow   fast
0      2      4
1      4      37
2      16     89
3      37     42
4      58     4
5      89     37
6      145    89
7      42     42    -> slow == fast, fast != 1 → false

Code

java

class Solution {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = next(n);
        while (fast != 1 && slow != fast) {
            slow = next(slow);          // one step
            fast = next(next(fast));    // two steps
        }
        return fast == 1;
    }

    private int next(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
}

Complexity

Time: O(log n) — same number of steps as before, up to a constant factor.
Space: O(1) — two integers.

Complexity Comparison

Approach	Time	Space
Hash Set	O(log n)	O(log n)
Floyd's Cycle Detection	O(log n)	O(1)

Common Pitfalls

Looping until n == 1 with no cycle check — unhappy numbers loop forever.
Starting slow and fast at the same value with a while (slow != fast) loop — the loop body never runs. Start fast one step ahead (or use do-while).
Returning slow == 1 — fast reaches 1 first; check fast.
Worrying about overflow: the digit-square sum of any int is at most 81 · 10 = 810, so it always fits.