# 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


/*solution1 use unordered_set,7ms*/
class Solution {
private:
int divideThenSum(int n){
int tmp=n,sum=0;
while(n){
tmp=n%10;
sum+=tmp*tmp;
n=n/10;
}
return sum;
}

public:
bool isHappy(int n) {
unordered_set<int> hash;
int res=n;
while(true){
res=divideThenSum(res);
if(hash.count(res)==0)
hash.insert(res);
else
return res==1;
}
}
};



AC之后又进行了更深一步的思考，既然是周期现象，那么也可以尝试一下Floyd Cycle Algorithm，即我们在判断链表是否有环时使用的算法(快慢指针法),代码如下:

/*solution 2,use Floyd cycle algorithm,4ms*/
class Solution {
private:
int divideThenSum(int n){
int tmp=n,sum=0;
while(n){
tmp=n%10;
sum+=tmp*tmp;
n=n/10;
}
return sum;
}

public:
bool isHappy(int n) {
int slow=n,fast=n;
do{
slow=divideThenSum(slow);
fast=divideThenSum(divideThenSum(fast));
}while(slow!=fast);
return slow==1;
}
};


### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017