LeetCode 202. Happy Number

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

翻譯

判斷一個數字是否為happy number。

happy number 定義如下：當一個數的每位數平方後相加，大於1則重複每位數開平方相加的動作，如果最後得到1的話，這個數就是happy number，如果進入無窮迴圈，這個數就不是happy number。

思路

使用一個map儲存計算過的數字，如果目前的數字已經計算過，表示無窮迴圈出現，return false。持續計算到1出現true或是無窮迴圈出現false。

範例：判斷4是不是happy number

4^2       = 16   
1^2 + 6^2 = 37  
3^2 + 7^2 = 58  
.....
......... = 20  
2^2 + 0   = 4  
4重複出現，因此進入無窮迴圈  

解題

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    // map儲存計算過的數字
    var store = {};

    // 如果map裡面出現過這個數字 或 數字 = 1，停止迴圈。
    while(!store[n] && n!=1){
        store[n] = n; 
        // 單純的計算毎一個位數的平方和
        n.toString().split("").forEach(function(v,i){
            if(i == 0) n = 0;
            n += v*v;
        })
        n = parseInt(n);
    }
    return n == 1;
};

Plus

• 以下這種寫法也可以，1~9之中，只有1,7是happy number
• 如果n超過10，計算到最後一定會落在1~9之中
• 判斷計算到最後的數字是不是1

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    while(n>6){
        n.toString().split("").forEach(function(v,i){
            if(i == 0) n = 0;
            n += v*v;
        })
    }
    return n == 1;
};