202. Happy Number

LeetCode

If a number is a “happy number”, it will eventually converge to 1, otherwise it will fall into a infinite “unhappy number” loop.

Thus we can use Floyd’s cycle detection algorithm to solve this problem. The slow pointer calculate the sum of digit square once per loop, and the fast pointer calculate the sum of digit square twice per loop, finally they will meet.

class Solution {
    private int digitSquareSum(int n) {
        int sum = 0;
        while (n != 0) {
            int tmp = n % 10;
            sum += tmp * tmp;
            n /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int slow = n;
        int fast = n;
        do {
            slow = digitSquareSum(slow);
            fast = digitSquareSum(fast);
            fast = digitSquareSum(fast);
        } while (slow != fast);
        
        return slow == 1;
    }
}