202. Happy Number

  • 39.8%

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

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
3
4
5
6
7
1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

方法一:

从开始,遍历过的放入set,如果再出现一次,则肯定为false,如果到1,返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool isHappy(int n) {
if(n<=0) return false;
if(n==1) return true;
unordered_set<int> set;
set.insert(n);
while(n!=1){
int sum = 0;
while(n!=0){
sum = sum + pow(n%10, 2);
n /= 10;
}
if(set.find(sum)!=set.end())
return false;
set.insert(sum);
n = sum;
}
return true;
}
};

另一种实现:

把一样放入table里,如果出现过,就判断是否等于1. 1的下一个还是1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
bool isHappy(int n) {
int num=0;
unordered_map<int,bool> table;
table[n]=1;
while(n!=1)
{
while(n)
{
num += (n%10) * (n%10);
n/=10;
}
if(table[num]) break;
else table[num]=1;
n=num;num=0;
}
return 1==n;
}
};

方法二:

比方法一差一些,因为没有保存,每次都去判断

1
2
3
4
5
6
7
8
9
10
11
12
13
bool isHappy(int n) {
int num=0;
while(n!=1&&n!=4)
{
while(n)
{
num += (n%10) * (n%10);
n/=10;
}
n=num;num=0;
}
return 1==n;
}

https://discuss.leetcode.com/topic/30520/explanation-of-why-those-posted-algorithms-are-mathematically-valid

Earlier posts gave the algorithm but did not explain why it is valid mathematically, and this is what this post is about: present a “short” mathematical proof.

First of all, it is easy to argue that starting from a number I, if some value - say a - appears again during the process after k steps, the initial number I cannot be a happy number. Because a will continuously become a after every k steps.

Therefore, as long as we can show that there is a loop after running the process continuously, the number is not a happy number.

There is another detail not clarified yet: For any non-happy number, will it definitely end up with a loop during the process? This is important, because it is possible for a non-happy number to follow the process endlessly while having no loop.

To show that a non-happy number will definitely generate a loop, we only need to show that for any non-happy number, all outcomes during the process are bounded by some large but finite integer N. If all outcomes can only be in a finite set (2,N], and since there are infinitely many outcomes for a non-happy number, there has to be at least one duplicate, meaning a loop!

Suppose after a couple of processes, we end up with a large outcome O1 with D digits where D is kind of large, say D>=4, i.e., O1 > 999 (If we cannot even reach such a large outcome, it means all outcomes are bounded by 999 ==> loop exists). We can easily see that after processing O1, the new outcome O2 can be at most 9^2D < 100D, meaning that O2 can have at most 2+d(D) digits, where d(D) is the number of digits D have. It is obvious that 2+d(D) < D. We can further argue that O1 is the maximum (or boundary) of all outcomes afterwards. This can be shown by contradictory: Suppose after some steps, we reach another large number O3 > O1. This means we process on some number W <= 999 that yields O3. However, this cannot happen because the outcome of W can be at most 9^23 < 300 < O1.

Done.

Please leave your comment if any question or suggestion.


cpp

https://discuss.leetcode.com/topic/38728/0ms-c-solution-beats-97-4-perhaps-the-most-easy-one-to-understand

I use three solutions: 1. hash table(8ms) 2. List circle detect method(4ms) 3.circle 1 and circle 4.
Here is the url:https://en.wikipedia.org/wiki/Happy_number Based on the fact that circle of 1 is happy, circle of 4 is unhappy.

Solution3:

1
2
3
4
5
6
7
8
9
10
11
12
13
bool isHappy(int n) {
int num=0;
while(n!=1&&n!=4)
{
while(n)
{
num += (n%10) * (n%10);
n/=10;
}
n=num;num=0;
}
return 1==n;
}

Solution1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
bool isHappy(int n) {
int num=0;
unordered_map<int,bool> table;
table[n]=1;
while(n!=1)
{
while(n)
{
num += (n%10) * (n%10);
n/=10;
}
if(table[num]) break;
else table[num]=1;
n=num;num=0;
}
return 1==n;
}
};

Solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
bool isHappy(int n) {
int slow,fast;
slow=fast=n;
do{
slow = compute(slow);
fast=compute(fast);
fast=compute(fast);
}while(slow!=fast);
return 1==slow;
}
private:
int compute(int n)
{
int num=0;
while(n)
{
num += (n%10) * (n%10);
n/=10;
}
return num;
}
};

python

Solution 1:

64ms, 42.28%, June.17th, 2016

https://leetcode.com/discuss/47623/my-python-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
mem = set()
while n != 1:
n = sum([int(i)**2 for i in str(n)])
if n not in mem:
mem.add(n)
else:
return False
return True

c

Solution 1:

0ms, 44.72%, June.17th, 2016

https://leetcode.com/discuss/33014/4ms-5-line-c-code

Using fact all numbers in [2, 6] are not happy (and all not happy numbers end on a cycle that hits this interval):

1
2
3
4
5
6
7
8
9
10
11
bool isHappy(int n) {
while(n>6){
int next = 0;
while(n){
next += (n%10) * (n%10);
n = n / 10;
}
n = next;
}
return n == 1;
}

https://discuss.leetcode.com/topic/12587/my-solution-in-c-o-1-space-and-no-magic-math-property-involved

I see the majority of those posts use hashset to record values. Actually, we can simply adapt the Floyd Cycle detection algorithm. I believe that many people have seen this in the Linked List Cycle detection problem. The following is my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int digitSquareSum(int n) {
int sum = 0, tmp;
while (n) {
tmp = n % 10;
sum += tmp * tmp;
n /= 10;
}
return sum;
}

bool isHappy(int n) {
int slow, fast;
slow = fast = n;
do {
slow = digitSquareSum(slow);
fast = digitSquareSum(fast);
fast = digitSquareSum(fast);
} while(slow != fast);
if (slow == 1) return 1;
else return 0;
}

java

https://discuss.leetcode.com/topic/25026/beat-90-fast-easy-understand-java-solution-with-brief-explanation

The idea is to use one hash set to record sum of every digit square of every number occurred. Once the current sum cannot be added to set, return false; once the current sum equals 1, return true;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public boolean isHappy(int n) {
Set<Integer> inLoop = new HashSet<Integer>();
int squareSum,remain;
while (inLoop.add(n)) {
squareSum = 0;
while (n > 0) {
remain = n%10;
squareSum += remain*remain;
n /= 10;
}
if (squareSum == 1)
return true;
else
n = squareSum;

}
return false;
}
}

https://discuss.leetcode.com/topic/12742/o-1-space-java-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public boolean isHappy(int n) {
int x = n;
int y = n;
while(x>1){
x = cal(x) ;
if(x==1) return true ;
y = cal(cal(y));
if(y==1) return true ;

if(x==y) return false;
}
return true ;
}
public int cal(int n){
int x = n;
int s = 0;
while(x>0){
s = s+(x%10)*(x%10);
x = x/10;
}
return s ;
}
}
谢谢你,可爱的朋友。