HappyNumber2 [source code]

public class HappyNumber2 {
static

public class Solution {
    public boolean isHappy(int n) {
        int res = n;
        while (res >= 10) {
            n = res;
            res = 0;
            while (n > 0) {
                int digit = n % 10;
                res += digit * digit;
                n = n / 10;
            }
        }
        return res == 1 || res == 7;
    }
}

    public static void main(String[] args) {
        HappyNumber2.Solution tester = new HappyNumber2.Solution();
        System.out.println(tester.isHappy(Integer.parseInt(args[0])));
    }
}

这个是根据我自己一开始瞎写的一个代码乱改改的, 结果最后居然过了, 而且是最优解1(97). 有点奇怪, 暂时我自己都不知道什么意思.

discussion 上面居然有一个人也是想到了这个方法, 不过好像并没有给出数学证明; 下面comment 给了一个证明, 但是各种毛病, 不过还是启发了一点思路;

他的做法大概就是: 假如我们用(num) 来代表num 的square sum:
if num has N digits and N >= 3:
(10^(N+1) - 1) = 9 9 N = 81N < 100N = 10^2 * N < 10^N - 1
也就是类似(9999) < 9999 / 10这样的结论;
num <= 10^(N+1) - 1;
(num) <= 10^N - 1;
应用起来就是找到 N, 比如1666, N=4, 所以(1666) < (9999) < 999;

这个思路还是没有问题的, 不过这个只能走到 N=3的位置, 再往下就不行了, 我们最后能证明所有的数最后都能走到两位数(注意他这里用上限99来表示两位数, 这个还是很聪明的).
这个证明的作者对此给出的结论是(99) = 162, 反正数字也不多, 枚举验证算了.

惊喜: 有人发现在 wiki 上就有证明.
这个证明有点粗糙, 在证明一定到达两位数上, 还用了一定的枚举.

An exhaustive search then shows that every number in the interval [1,99] either is happy or goes to the above cycle.
所以还是靠穷举做的. 这里的 cycle 指的是:
Numbers that are happy follow a sequence that ends in 1. All non-happy numbers follow sequences that reach the cycle:
4, 16, 37, 58, 89, 145, 42, 20, 4, ...
这个有点失望.

后面给出了一个结论:

The above work produces the interesting result that no positive integer other than 1 is the sum of the squares of its own digits, since any such number would be a fixed point of the described process.

另外, 既然其实我们判断的就是4, 干脆直接就把代码改成判断4也可以(当然是≥10以上情况);

这个是 discussion 上面另外一个类似的思路, 不过我感觉这个证明比我这个还要困难:

bool isHappy(int n) {  
    while(n>6){  
        int next = 0;  
        while(n){next+=(n%10)*(n%10); n/=10;}  
        n = next;  
    }  
    return n==1;  
}

Problem 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 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
Credits:
Special thanks to @mithmatt and @ts for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:40.36%
Contributor: LeetCode
Companies
uber airbnb twitter
Related Topics
hash table math
Similar Questions
Add Digits Ugly Number