202. Happy Number (Easy)

Problem

A number n is happy if repeatedly replacing it with the sum of squares of its digits eventually reaches 1. If the sequence enters a cycle without hitting 1, n is not happy.

Example

• n = 19 → true (1² + 9² = 82 → 68 → 100 → 1)
• n = 2 → false

LeetCode 202 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Hash set of seen values

Repeatedly apply the operation; if you revisit, it’s a cycle (not happy). If you reach 1, it’s happy.

Python

def is_happy(n):
    def next_n(x):
        return sum(int(d) ** 2 for d in str(x))    # L1: O(log x) digits

    seen = set()
    while n != 1 and n not in seen:                 # L2: loop k iterations
        seen.add(n)                                 # L3: O(1) amortized
        n = next_n(n)                               # L4: O(log n)
    return n == 1

TypeScript

function isHappy(n: number): boolean {
    function nextN(x: number): number {
        return String(x).split('').reduce((sum, d) => sum + +d * +d, 0);  // L1: O(log x)
    }
    const seen = new Set<number>();
    while (n !== 1 && !seen.has(n)) {              // L2: loop k iterations
        seen.add(n);                               // L3: O(1) amortized
        n = nextN(n);                              // L4: O(log n)
    }
    return n === 1;
}

Go

func isHappy(n int) bool {
    nextN := func(x int) int {
        total := 0
        for x != 0 { d := x % 10; total += d * d; x /= 10 }  // L1: O(log x)
        return total
    }
    seen := map[int]bool{}
    for n != 1 && !seen[n] {                       // L2: loop k iterations
        seen[n] = true                             // L3: O(1) amortized
        n = nextN(n)                               // L4: O(log n)
    }
    return n == 1
}

Swift

final class Solution {
    func isHappy(_ n: Int) -> Bool {
        var seen: Set<Int> = []
        var current = n
        while current != 1 && seen.insert(current).inserted {
            current = digitSquareSum(current)
        }
        return current == 1
    }

    private func digitSquareSum(_ value: Int) -> Int {
        var value = value, total = 0
        while value > 0 { let digit = value % 10; total += digit * digit; value /= 10 }
        return total
    }
}

Where the time goes, line by line

Variables: n = the input integer, k = number of iterations until cycle or 1 (bounded constant for inputs fitting 32 bits).

Line	Per-call cost	Times executed	Contribution
L1 (digit sum)	$O(log x)$	k	$O(k · log n)$
L2 (loop guard)	$O(1)$	k	$O(k)$
L3, L4 (add + next)	$O(log n)$	k	$O(k · log n)$ ← dominates

For 32-bit integers, after one step the value drops below 9999 (at most 4 digits each squared = max 324), so k is effectively bounded by a small constant. In practice this is $O(log n)$ total.

Complexity

• Time: $O(log n · k)$ where k is the number of iterations.
• Space: $O(k)$ for the seen set.

Approach 2: Floyd’s tortoise and hare (canonical, $O(1)$ space)

Treat the sequence as a linked list. If it cycles (not happy), the two pointers meet.

Python

def is_happy(n):
    def next_n(x):
        total = 0
        while x:                        # L1: O(log x) digit extraction
            total += (x % 10) ** 2
            x //= 10
        return total

    slow = fast = n
    while True:
        slow = next_n(slow)             # L2: one step
        fast = next_n(next_n(fast))     # L3: two steps
        if fast == 1:
            return True                 # L4: happy
        if slow == fast:
            return False                # L5: cycle detected

TypeScript

function isHappy(n: number): boolean {
    function nextN(x: number): number {
        let total = 0;
        while (x) {                     // L1: O(log x) digit extraction
            total += (x % 10) ** 2;
            x = Math.floor(x / 10);
        }
        return total;
    }

    let slow = n, fast = n;
    while (true) {
        slow = nextN(slow);             // L2: one step
        fast = nextN(nextN(fast));      // L3: two steps
        if (fast === 1) return true;    // L4: happy
        if (slow === fast) return false; // L5: cycle detected
    }
}

Go

func isHappy(n int) bool {
    nextN := func(x int) int {
        total := 0
        for x != 0 { d := x % 10; total += d * d; x /= 10 }  // L1: O(log x)
        return total
    }
    slow, fast := n, n
    for {
        slow = nextN(slow)              // L2: one step
        fast = nextN(nextN(fast))       // L3: two steps
        if fast == 1 { return true }    // L4: happy
        if slow == fast { return false } // L5: cycle detected
    }
}

Swift

final class Solution {
    func isHappy(_ n: Int) -> Bool {
        var slow = n, fast = digitSquareSum(n)
        while fast != 1 && slow != fast {
            slow = digitSquareSum(slow)
            fast = digitSquareSum(digitSquareSum(fast))
        }
        return fast == 1
    }

    private func digitSquareSum(_ value: Int) -> Int {
        var value = value, total = 0
        while value > 0 { let digit = value % 10; total += digit * digit; value /= 10 }
        return total
    }
}

Where the time goes, line by line

Variables: n = the input integer, k = iterations until slow and fast meet (bounded constant for 32-bit inputs).

Line	Per-call cost	Times executed	Contribution
L1 (digit extraction)	$O(log x)$	k	$O(k · log n)$
L2, L3 (slow/fast advance)	$O(log n)$	k	$O(k · log n)$ ← dominates
L4, L5 (termination checks)	$O(1)$	k	$O(k)$

Same asymptotic cost as Approach 1; the win is space, not time.

Complexity

• Time: Same as Approach 1.
• Space: $O(1)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Mathematical shortcut

Every non-happy cycle contains 4. So if you ever see 4, return false.

Python

def is_happy(n):
    def next_n(x):
        total = 0
        while x:
            total += (x % 10) ** 2
            x //= 10
        return total

    while n != 1 and n != 4:           # L1: loop until 1 or known cycle marker
        n = next_n(n)                   # L2: O(log n)
    return n == 1

Swift

final class Solution {
    func isHappy(_ n: Int) -> Bool {
        var current = n
        while current >= 10 { current = digitSquareSum(current) }
        return current == 1 || current == 7
    }

    private func digitSquareSum(_ value: Int) -> Int {
        var value = value, total = 0
        while value > 0 { let digit = value % 10; total += digit * digit; value /= 10 }
        return total
    }
}

Where the time goes, line by line

Variables: n = the input integer, k = iterations until 1 or 4 (bounded constant for 32-bit inputs).

Line	Per-call cost	Times executed	Contribution
L1, L2 (loop)	$O(log n)$	k	$O(k · log n)$ ← dominates

Same cost as Approaches 1 and 2; the “check for 4” is just a constant-factor improvement on the exit condition.

Complexity

• Time: $O(log n · k)$.
• Space: $O(1)$.

Why 4 works

For any number ≤ 9999, the happy iteration either reaches 1 or enters the cycle 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → .... For larger numbers, one iteration brings them under 9999. Any unhappy number eventually hits 4; happy numbers don’t.

Summary

Approach	Time	Space
Hash set	$O(log n · k)$	$O(k)$
Floyd’s cycle detection	$O(log n · k)$	$O(1)$
”Check for 4” shortcut	$O(log n · k)$	$O(1)$

Floyd’s is the generalizable answer (applies to any deterministic next-state sequence); the “4 trick” is the cutest.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_202.py and run.
# Uses the canonical implementation (Approach 2: Floyd's cycle detection).

def is_happy(n):
    def next_n(x):
        total = 0
        while x:
            total += (x % 10) ** 2
            x //= 10
        return total
    slow = fast = n
    while True:
        slow = next_n(slow)
        fast = next_n(next_n(fast))
        if fast == 1:
            return True
        if slow == fast:
            return False

def _run_tests():
    assert is_happy(19) == True
    assert is_happy(2) == False
    assert is_happy(1) == True     # 1 is trivially happy
    assert is_happy(7) == True     # 7 is happy (7->49->97->130->10->1)
    assert is_happy(4) == False    # 4 is the cycle entry for unhappy numbers
    assert is_happy(100) == True   # 1^2+0+0 = 1 immediately
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function isHappy(n: number): boolean {
    function nextN(x: number): number {
        let total = 0;
        while (x) { total += (x % 10) ** 2; x = Math.floor(x / 10); }
        return total;
    }
    let slow = n, fast = n;
    while (true) {
        slow = nextN(slow);
        fast = nextN(nextN(fast));
        if (fast === 1) return true;
        if (slow === fast) return false;
    }
}

console.assert(isHappy(19) === true);
console.assert(isHappy(2) === false);
console.assert(isHappy(1) === true);
console.assert(isHappy(7) === true);
console.assert(isHappy(4) === false);
console.assert(isHappy(100) === true);
console.log('all tests pass');

Related data structures

• Linked Lists, Floyd’s on a numeric sequence treated as a linked list
• Hash Tables, seen-set variant

Related concepts

• Cycle Detection, repeated-state tactics for finding loops in linked lists, graphs, arrays, and numeric processes.
• Fast and Slow Pointers, pointer-speed tactics for cycle detection, middle finding, and linked-list distance constraints.
• Math and Number Theory, arithmetic tactics for problems driven by divisibility, digits, modular behavior, and numeric identities.