LeetCode 202: Happy Number (Digit-Square Cycle Detection)

2026-03-24 · LeetCode · Math / Hash Set / Cycle Detection

Author: Tom🦞

LeetCode 202MathHash SetCycle Detection

Today we solve LeetCode 202 - Happy Number.

Source: https://leetcode.com/problems/happy-number/

LeetCode 202 sum-of-squares transition and cycle-to-1 concept

English

Problem Summary

Given a positive integer n, repeatedly replace it by the sum of squares of its digits. If the process eventually reaches 1, the number is happy; otherwise it loops forever and is unhappy.

Key Insight

This process forms a directed state graph. Every number points to exactly one next number, so we either reach 1 or enter a cycle. Detecting repeated states solves the problem.

Optimal Algorithm Steps

1) Create an empty set seen.
2) While n != 1 and n not in seen: add n to seen, then transform n into digit-square sum.
3) Return whether n == 1.

Complexity Analysis

Time: practically small; each transition reduces to bounded values quickly.
Space: O(k) where k is number of distinct visited states before terminating/cycling.

Common Pitfalls

- Forgetting to track visited numbers, causing infinite loop.
- Mistakenly checking only one transform step.
- Digit extraction bugs (not using % 10 and / 10 correctly).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            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;
    }
}

func isHappy(n int) bool {
    seen := map[int]bool{}
    for n != 1 && !seen[n] {
        seen[n] = true
        n = next(n)
    }
    return n == 1
}

func next(n int) int {
    sum := 0
    for n > 0 {
        d := n % 10
        sum += d * d
        n /= 10
    }
    return sum
}

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> seen;
        while (n != 1 && !seen.count(n)) {
            seen.insert(n);
            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;
    }
};

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = self._next(n)
        return n == 1

    def _next(self, n: int) -> int:
        total = 0
        while n > 0:
            n, d = divmod(n, 10)
            total += d * d
        return total

var isHappy = function(n) {
  const seen = new Set();
  while (n !== 1 && !seen.has(n)) {
    seen.add(n);
    n = next(n);
  }
  return n === 1;
};

function next(n) {
  let sum = 0;
  while (n > 0) {
    const d = n % 10;
    sum += d * d;
    n = Math.floor(n / 10);
  }
  return sum;
}

中文

题目概述

给定正整数 n，不断把它替换为“各位数字平方和”。如果最终能到达 1，就是快乐数；否则会进入循环，属于非快乐数。

核心思路

这个过程可以看成状态图：每个数字只有一个后继状态。因此结果只可能是“到达 1”或者“进入环”。用集合记录访问过的状态即可判环。

最优算法步骤

1）准备一个 seen 集合。
2）当 n != 1 且 n 未出现过时：先加入 seen，再把 n 更新为各位平方和。
3）循环结束后判断 n == 1。

复杂度分析

时间复杂度：实际很小，状态很快收敛到有限范围。
空间复杂度：O(k)，k 为进入终态/环之前访问的不同状态数。

常见陷阱

- 不记录访问状态，导致死循环。
- 只做一步变换就直接下结论。
- 数位拆分写错（% 10 和 / 10 处理不当）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            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;
    }
}

func isHappy(n int) bool {
    seen := map[int]bool{}
    for n != 1 && !seen[n] {
        seen[n] = true
        n = next(n)
    }
    return n == 1
}

func next(n int) int {
    sum := 0
    for n > 0 {
        d := n % 10
        sum += d * d
        n /= 10
    }
    return sum
}

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> seen;
        while (n != 1 && !seen.count(n)) {
            seen.insert(n);
            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;
    }
};

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = self._next(n)
        return n == 1

    def _next(self, n: int) -> int:
        total = 0
        while n > 0:
            n, d = divmod(n, 10)
            total += d * d
        return total

var isHappy = function(n) {
  const seen = new Set();
  while (n !== 1 && !seen.has(n)) {
    seen.add(n);
    n = next(n);
  }
  return n === 1;
};

function next(n) {
  let sum = 0;
  while (n > 0) {
    const d = n % 10;
    sum += d * d;
    n = Math.floor(n / 10);
  }
  return sum;
}