202. Happy Number

題目 / Problem

中文：寫一個演算法判斷一個數字 n 是不是「快樂數」。快樂數的定義是這樣的：從任意正整數開始，把這個數換成「它各個位數的平方和」。不斷重複這個過程——如果最後變成 1（並一直停在 1），那它就是快樂數；如果它陷入一個永遠不包含 1 的循環，那就不是。是快樂數回傳 true，否則回傳 false。

English: Determine whether a number n is a happy number. Starting from a positive integer, repeatedly replace it with the sum of the squares of its digits. If this process eventually reaches 1 (and stays there), n is happy → return true. If it instead falls into a cycle that never contains 1, return false.

Constraints: 1 <= n <= 2^31 - 1（即 n 最大約 21 億，是一個 32-bit 範圍內的正整數 / n fits in a signed 32-bit integer）。

Worked example: n = 19 - 1² + 9² = 1 + 81 = 82 - 8² + 2² = 64 + 4 = 68 - 6² + 8² = 36 + 64 = 100 - 1² + 0² + 0² = 1 ✅ → 快樂數 / happy → true

名詞解釋 / Glossary

• 各位數平方和 / sum of squares of digits：把數字拆成一個個位數，每個位數平方後加總。例如 82 → 8² + 2² = 68。This is the core transformation applied at each step.
• 循環偵測 / cycle detection：判斷一連串數值會不會繞回到之前出現過的值。如果繞回去了，表示我們進入了無限循環。Detecting whether a sequence of values revisits a previous value.
• 雜湊集合 / hash set：一種能在「平均 O(1) 時間」內判斷某個元素是否已經出現過的資料結構。C++ 裡是 unordered_set，C 裡我們用一個布林陣列或自己開的雜湊表模擬。A data structure that answers "have I seen this value before?" in O(1) average time.
• 快慢指針 / Floyd's two pointers (tortoise & hare)：一種不需要額外記憶體的循環偵測技巧。讓兩個「指針」以不同速度（一步、兩步）沿著序列前進，若兩者相遇即代表有循環。A constant-space cycle-detection trick where two runners move at different speeds; if they meet, there's a cycle.
• 不變量 / invariant：演算法執行過程中始終成立的性質，用來保證正確性。A property that always holds during the algorithm, used to argue correctness.

思路

最直接的想法（brute force）是：不斷算「各位數平方和」，如果某次得到 1 就回傳 true。問題在於——如果這個數永遠到不了 1，它會無限跑下去，程式根本不會停。所以真正的難點不是計算平方和（那很簡單），而是怎麼知道該停下來。關鍵觀察是：這個過程一定會重複出現某個值，因為平方和不會無限變大。對一個任意大的數，它的位數有限，每次平方和最多也就幾百（例如三位數最大 999 → 243），所以數值會被「壓」進一個很小的範圍。在這個有限範圍內不斷跳，要嘛跳到 1，要嘛遲早會跳回一個出現過的數，形成循環。於是我們用一個雜湊集合記錄每個出現過的值：每算出新值就檢查它是否已經在集合裡——若等於 1 回傳 true，若已出現過代表進入循環回傳 false，否則把它存進集合繼續算。這裡的不變量是「集合裡存的都是過去走過的值」，所以一旦重複就能立刻判定循環。

The brute-force idea is simply: keep computing the digit-square-sum and return true the moment you hit 1. The trouble is termination — if the number never reaches 1, the loop runs forever. So the real challenge isn't the arithmetic (that's trivial), it's knowing when to stop. The key insight is that the sequence of values must eventually repeat, because the digit-square-sum can't grow without bound: any number gets squeezed into a small range (a 3-digit number maps to at most 999 → 243), and within that finite range you either reach 1 or revisit a value you've already produced. We exploit this with a hash set that remembers every value seen: each new value is checked — equal to 1 → true; already in the set → we've found a cycle → false; otherwise insert it and continue. The invariant "the set contains exactly the previously-visited values" guarantees that the first repeat correctly signals a non-terminating cycle. (An alternative is Floyd's two-pointer cycle detection, which uses O(1) memory; I'll mention it but use the clearer hash-set version as the main solution.)

逐步走查 / Walkthrough

輸入 / Input: n = 19。我們用一個雜湊集合 seen 記錄看過的值。

每一輪我們先檢查目前的 n：若是 1 就成功結束；若已在 seen 裡就代表循環、失敗結束；否則記錄它，再把 n 換成它的平方和。19 在第 5 輪變成 1，所以是快樂數。

Each round we first inspect the current n: if it's 1 we succeed; if it's already in seen we've hit a cycle and fail; otherwise we record it and replace n with its digit-square-sum. For 19, the value becomes 1 on step 5, so it's happy.

Solution — C

// 演算法 / Algorithm:
// 反覆把 n 換成「各位數平方和」，用雜湊集合記錄看過的值。
// Repeatedly map n to its digit-square-sum; a hash set records seen values.
// 遇到 1 → 快樂數 (true)；遇到重複值 → 進入循環 (false)。
// Hit 1 → happy (true); hit a repeated value → cycle (false).

#include <stdbool.h>   // 提供 bool / true / false 型別 / provides the bool type
#include <stdlib.h>    // 提供 calloc 與 free / provides calloc and free

// 輔助函式：計算一個數各位數的平方和 / Helper: sum of squares of n's digits
static int squareDigitSum(int n) {
    int sum = 0;                 // 累加器，存平方和 / accumulator for the running sum
    while (n > 0) {              // 逐位處理，直到把所有位數取完 / loop until every digit is consumed
        int d = n % 10;         // n % 10 取出最低位的數字 / n % 10 extracts the last digit
        sum += d * d;           // 平方後加進 sum / square it and add to the total
        n /= 10;                // n /= 10 砍掉最低位（整數除法）/ integer-divide to drop that digit
    }
    return sum;                 // 回傳這一輪的平方和 / return this round's sum
}

bool isHappy(int n) {
    // 平方和最後一定落在很小的範圍，最大值約 243（999→243），
    // 但 n 第一步可能很大，之後就被壓到 < 1000，所以開 1000 大小的標記陣列足夠。
    // After the first step values stay < 1000, so a 1000-slot seen[] table is enough.
    // calloc 配置記憶體並全部清零；每格代表「該值是否出現過」。
    // calloc allocates zero-initialized memory; seen[v] marks whether value v appeared.
    bool *seen = calloc(1000, sizeof(bool));   // 動態配置布林陣列 / dynamically allocate a bool array

    while (n != 1) {                 // 只要還沒到 1 就繼續 / keep going until we reach 1
        if (n < 1000 && seen[n]) {  // n 已在範圍內且曾出現過 → 循環 / value seen before → cycle
            free(seen);             // 釋放記憶體，避免洩漏 / free memory to avoid a leak
            return false;           // 不是快樂數 / not happy
        }
        if (n < 1000) {             // 只有落入小範圍的值才需要、也才能標記 / only small values are marked
            seen[n] = true;         // 記錄這個值已出現 / record this value as seen
        }
        n = squareDigitSum(n);      // 換成下一個值 / advance to the next value in the sequence
    }

    free(seen);                     // 迴圈結束代表 n==1，先釋放再回傳 / n reached 1; free then return
    return true;                    // 是快樂數 / it is a happy number
}

Solution — C++

// 演算法 / Algorithm:
// 反覆把 n 換成「各位數平方和」，用 unordered_set 記錄看過的值。
// Repeatedly map n to its digit-square-sum; an unordered_set records seen values.
// 遇到 1 → 快樂數；遇到重複值 → 循環，回傳 false。
// Reach 1 → happy; revisit a value → cycle → false.

#include <unordered_set>   // 提供雜湊集合 unordered_set / provides the hash-set container

class Solution {
public:
    bool isHappy(int n) {
        // unordered_set<int> 是雜湊集合，insert / count 平均 O(1)。
        // unordered_set<int> is a hash set with average O(1) insert and lookup.
        std::unordered_set<int> seen;

        // 迴圈條件：n 不是 1，且 n 還沒出現過。
        // Loop while n is neither 1 nor a value we've already seen.
        // seen.count(n) 回傳 n 在集合中的個數（0 或 1），當作「是否存在」用。
        // seen.count(n) returns 0 or 1, used here as a "does it exist?" test.
        while (n != 1 && seen.count(n) == 0) {
            seen.insert(n);          // 把目前的 n 記下來 / remember the current value
            n = squareDigitSum(n);   // 換成下一個值 / move to the next value
        }

        // 跳出迴圈有兩種可能：n==1（快樂）或 n 是重複值（循環）。
        // We exit either because n == 1 (happy) or because n repeated (cycle).
        return n == 1;               // 只有 n 恰好是 1 才回傳 true / true only when n is exactly 1
    }

private:
    // 計算各位數平方和 / compute the sum of squares of n's digits
    int squareDigitSum(int n) {
        int sum = 0;                 // 平方和累加器 / accumulator
        while (n > 0) {              // 逐位取出，直到取完 / process each digit
            int d = n % 10;          // 取最低位 / last digit via modulo
            sum += d * d;            // 平方後累加 / add its square
            n /= 10;                 // 去掉最低位 / drop that digit
        }
        return sum;                  // 回傳結果 / return the sum
    }
};

複雜度 / Complexity

• Time: O(log n) — 第一次計算平方和需要走過 n 的每一位，位數約為 log₁₀(n)。之後數值會被壓到 1000 以下的小範圍，後續步數有一個常數上界（在那個小範圍內最多跳固定次數就會到 1 或開始循環）。所以主導項是第一步的位數處理。The first digit-sum costs O(log n) over n's digits; afterwards values stay below 1000, so the remaining number of steps is bounded by a constant. The log n digit processing dominates.
• Space: O(log n) —（雜湊集合版）最多存進約幾十個不同的值就會終止，可視為常數級；嚴格上界與數值範圍有關。C 版用固定 1000 格陣列，是 O(1)。The hash set holds at most a small (effectively constant) number of distinct values before termination; the C array is a fixed 1000 slots, O(1).

Pitfalls & Edge Cases

• 無限迴圈 / Infinite loop：最大的陷阱。若只判斷「是否等於 1」而不偵測循環，非快樂數（如 n = 2）會讓程式永遠跑下去。本解用 seen 集合在第一次重複時就停下。Without cycle detection, non-happy inputs never terminate; the seen set stops at the first repeat.
• n = 1：邊界情況。1 本身就是快樂數，迴圈條件 n != 1 一開始就為假，直接回傳 true，正確。n = 1 is happy by definition; the loop body never runs and we return true.
• C 版陣列大小 / C array bound：別把 seen 開太小或忘了 n < 1000 的檢查——n 第一步可能高達 21 億，若直接用 seen[n] 會越界存取。程式只在 n < 1000 時才讀寫陣列。Never index seen[n] when n can be ~2 billion; we guard every access with n < 1000.
• 整數溢位 / Overflow：不用擔心。各位數平方和最多 9² × 10位 = 810，遠在 int 範圍內，所以不會溢位。The square-sum is tiny (≤ ~810), far within int, so no overflow risk.
• 記憶體釋放 / Freeing memory：C 版每條回傳路徑都要 free(seen)，否則造成記憶體洩漏。Every return path in the C version frees seen to avoid a leak.