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^2 + 9^2 = 82$
$8^2 + 2^2 = 68$
$6^2 + 8^2 = 100$
$1^2 + 0^2 + 0^2 = 1$
意思：判断一个整数的所有数字平方和Sum是否为1，如果不是循环计算Sum的所有数字的平方和，要么最终得到1、要么无限循环。如果是1就是happyNum。

算法思想

计算过程中用hashtable存储不是happyNumber的数字，每次计算之前查表判断是否为happyNum。如果不是happyNum就循环计算，如果是则停止。

算法实现

import java.util.Hashtable;

public class Solution {
    public boolean isHappy(int n) {
        boolean happyNum = false;
        Hashtable<Integer, Boolean> badNumDic = new Hashtable<Integer, Boolean>();
        int sum = 0;
        while (!happyNum) {
            sum = 0;
            while (n > 0) {
                sum += (n % 10) * (n % 10);
                n = n / 10;
            }
            System.out.println(sum);
            if (sum != 1) {
                if (badNumDic.containsKey(sum))
                    break;
                badNumDic.put(sum, false);
            } else {
                happyNum = true;
            }
            n = sum;
        }
        return happyNum;
    }
}

算法时间

这里表面看上去时间复杂度为两层循环，实际上：

1. 外层循环的计算是一个有限常量

例如随便给一个数25，他的计算过程如下：
1^2+9^2 = 29
2^2+9^2 = 85
8^2 + 5^2 = 89
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 4
4^2 = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89(和第三步相同，如此反复，而在程序中由于我们存储在hashtable中，所以至此结束)

1. 内层循环至多为最大整数2147483647的位数10，同样为常量

运行时间为T(n) = O(1)

演示结果

public static void main(String[] args) {
        Solution hn = new Solution();
        System.out.println(hn.isHappy(11111));
    }

5
25
29
85
89
145
42
20
4
16
37
58
89
false