Happy Number

• Happy Number
  • 题目描述
  • 解法

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² + 9² = 82

• 8² + 2² = 68

• 6² + 8² = 100

• 1² + 0² + 0² = 1

解法

代码如下:

public static boolean isHappy( int n ) {
    int slow = n, fast = n;
    do {
        slow = next( slow );
        fast = next( fast );
        fast = next( fast );
    } while( slow != fast );
    return slow == 1;
}
private static int next( int n ) {
    int sum = 0;
    while( n != 0 ) {
        int mod = n % 10;
        sum += mod * mod;
        n /= 10;
    }
    return sum;
}

思考过程: 根据题意, 可以知道经过不断的处理, 一定会形成一个环, 要么是一个很多元素的环(非Happy Number), 要么是一个元素的环(Happy Number). 所以这道题可以使用快慢指针来处理. 算法参考自这里

时空复杂度: 时间复杂度是O(n), 空间复杂度是O(1)