202. Happy Number

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

快樂數的定義： 將各位數平方後相加，若不斷重覆後最終停在結果為 1，則此數為快樂數，反之不是

例如 19 是快樂數
$1^2 + 9^2 = 1 + 81 = 82$
$8^2 + 2^2 = 64 + 4 = 68$
$6^2 + 8^2 = 36 + 64 = 100$
$1^2 + 0^2 + 0^2 = 1 + 0 + 0 = 1$
最終結果停在 1，所以 19 是快樂數

要算出 n 的各位數平方相加並不難
問題在於，程式該如何判斷何時要停止計算？

一個直覺想法是當出現了重覆的計算結果時，便知道不必再繼續計算
所以可以設計一個 hash set 來記錄計算結果

但是假如是數字會越算越大呢？

經過推敲便可知道這件事不會發生
假設給定一個很大的數字，例如 9999999999999(13 個 9)，則計算一次的快樂數即為 $81 * 13 = 1053$
因此可以得知，再怎麼大的數字都只會越計算越小而已

Takeaway

無