202. Happy Number

Question

Write an algorithm to determine if a number n 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.
• 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.

Return true if n is a happy number, and false if not.

Solution

首先证明，快乐数的计算不会趋近于无穷大。
我们可以考虑每一个位数的最大数字（9999…999）。
其下一个数值等于(81*n)。
对于三位数以下，其最大的值得下一个结果不会大于243。
对于四位数以上，下一个结果会快速收缩到三位数。
因此计算结果不会趋近于无穷。

当我们计算快乐数的值时，形成了一个隐式链表。
因此我们可以用快慢指针的方式，查询链表上是否有环。
快指针比慢指针初始值快1个单位，且移动速度为慢指针的一倍。
如果链表中有环，则两者终能相遇。
如果fast指针先走到1，等于走到了链表的终点。

Code

class Solution {
    public boolean isHappy(int n) {
        int slow = n, fast = getNext(n);
        while(fast != 1 && fast != slow){
            fast = getNext(getNext(fast));
            slow = getNext(slow);
        }
        return fast == 1;
    }
    
    private int getNext(int n){
        int sum = 0;
        while(n != 0){
            int digit = n % 10;
            sum += (digit * digit);
            n = n / 10;
        }
        return sum;
    }
}