// 演算法 / 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
}