Happy Number

EasyFast & Slow Pointers · Hashing🧩 Fast & Slow Pointers LeetCode #202 ↗Updated Oct 30, 2026

Problem

Start from a positive integer n and keep replacing it with the sum of the squares of its digits. If this process eventually reaches 1 the number is happy; if it gets stuck looping forever without hitting 1, it is not. Return true exactly when n is happy.

Inputn = 19Outputtrue (19 → 82 → 68 → 100 → 1)

Inputn = 2Outputfalse (falls into the loop 4 → 16 → ... → 4)

1 ≤ n ≤ 2³¹ - 1

Try it yourself

Java

class Solution {
    public boolean isHappy(int n) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The digit-square map turns n into an implicit linked list (each value points to its successor). Values quickly shrink below a few hundred, so the list must either reach 1 or enter a cycle — a cycle-detection problem in disguise.

PatternFast & Slow Pointers

Instinct A next-step function you can follow (list nodes, digit-square sums, array-as-pointers) and you need a cycle, its entry, or the middle in O(1) space.

Memory hack Tortoise and hare - on a loop track the hare laps the tortoise; restart the tortoise at the gate and they meet at the loop's door.

Open the Fast & Slow Pointers guide →

Approaches

Brute ForceSimulate & Remember Seen Values (HashSet)

Time O(log n)Space O(log n)

Walk the sequence and store every value in a set. Reaching 1 means happy; meeting a value we already stored means we are going round a loop that can never contain 1 (since 1 maps to itself). The first step costs O(log n) digits, after which every value stays below 1000, so the walk is short.

Java

public boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    while (n != 1 && seen.add(n)) { // add() is false once n repeats
        n = next(n);
    }
    return n == 1;
}

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

Direct and obviously correct, but keeps every visited value in memory.

OptimalFloyd’s Tortoise & Hare

Time O(log n)Space O(1)

Run two walkers over the same sequence: slow takes one step, fast takes two. If a cycle exists the hare laps the tortoise and they meet; if the number is happy both end up parked at 1 (a self-loop). So just check whether the meeting point is 1.

Java

public boolean isHappy(int n) {
    int slow = n, fast = next(n);
    while (fast != 1 && slow != fast) {
        slow = next(slow);
        fast = next(next(fast)); // hare moves twice as fast
    }
    return fast == 1;
}

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

Dry runn = 19

s slowf fast changed

start
19
s
82
f
68

100

1

slow=19, fast=82
step 1
19

82
s
68

100
f
1

fast jumps 2
step 2
19

82

68
s
100

1
f
fast reached 1
stop
19

82

68

100

1
f
return true ✔

Same speed as the set, but constant memory — the expected answer.

Pro tip

Every unhappy number falls into the single loop containing 4, so while (n != 1 && n != 4) also works — but explain Floyd first.

At a glance

Level	Approach	Time	Space
Brute Force	Simulate & Remember Seen Values (HashSet)	`O(log n)`	`O(log n)`
Optimal	Floyd’s Tortoise & Hare	`O(log n)`	`O(1)`

Common pitfalls

Looping until n == 1 with no cycle check — unhappy inputs never terminate.
Floyd: starting slow and fast equal makes the loop exit immediately.
Fearing overflow — the digit-square sum of any int is at most 9²×10 = 810.

Interview tips

Say out loud that the sequence is bounded, so it must repeat or hit 1.
Present the HashSet version first, then upgrade to O(1) space with Floyd.
Reuse a tiny next() helper for clean, testable code.

Pattern

Floyd cycle detection on an implicit sequence → any repeated deterministic transformation that may loop.

My notes saved in this browser