Problem
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:
Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Solution 1
/**
* @param {number} n
* @return {boolean}
*/
var isHappy = function(n) {
var map = {};
var tmp = 0;
if (n < 1) return false;
while (n !== 1 && !map[n]) {
map[n] = true;
tmp = 0;
while (n > 0) {
tmp += Math.pow(n % 10, 2);
n = Math.floor(n / 10);
}
n = tmp;
}
return n === 1;
};
Explain:
nope.
Complexity:
- Time complexity :
- Space complexity :
Solution 2
/**
* @param {number} n
* @return {boolean}
*/
var isHappy = function(n) {
var fast = n;
var slow = n;
if (n < 1) return false;
do {
slow = getsumsquare(slow);
fast = getsumsquare(getsumsquare(fast));
} while (slow !== fast);
return slow === 1;
};
var getsumsquare = function (n) {
var sum = 0;
var tmp = 0;
while (n > 0) {
tmp = n % 10;
sum += tmp * tmp;
n = Math.floor(n / 10);
}
return sum;
};
Explain:
两种情况:有 1
和 循环。
循环的时候,在一个圈里,两人在相同的地方同时出发,一个人每次走一步,另一个人每次走两步,他们肯定会再相遇。
有 1
的时候,两人都会停留在 1
。
Complexity:
- Time complexity :
- Space complexity :