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
很自然的解法是：
class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ def sum2(num): ans = 0 while num != 0: ans += (num % 10)**2 num = num/10 return ans m = set() while n not in m: if n == 1: return True m.add(n) n = sum2(n) return False
还有可以使用环路链表的判断方法，一个快慢指针一起赛跑，直到追上：
class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ def sum2(num): ans = 0 while num != 0: ans += (num % 10)**2 num = num/10 return ans slow = n fast = sum2(sum2(n)) while slow != fast: slow = sum2(slow) fast = sum2(sum2(fast)) return slow == 1
java代码其实非常优雅：
int digitSquareSum(int n) { int sum = 0, tmp; while (n) { tmp = n % 10; sum += tmp * tmp; n /= 10; } return sum;}bool isHappy(int n) { int slow, fast; slow = fast = n; do { slow = digitSquareSum(slow); fast = digitSquareSum(fast); fast = digitSquareSum(fast); } while(slow != fast); if (slow == 1) return 1; else return 0;}数学解法：
class Solution {public:int loop[8] = {4,16,37,58,89,145,42,20};bool inLoop(int n){ for(auto x: loop){ if(x == n) return true; } return false;}bool isHappy(int n) { if(n == 1) return true; if(inLoop(n)) return false; int next = 0; while(n){ next += (n%10)*(n%10); n /= 10; } return isHappy(next);}};
proof:1.loop number is less than 162.Assume f(x) is the sum of the squares of x’s digits. let’s say 0 < x <= 9,999,999,999 which is larger than the range of an int. f(x) <= 9^2 * 10 = 810. So no mater how big x is, after one step of f(x), it will be less than 810.The most large f(x) value (x < 810) is f(799) = 211. And do this several times: f(211) < f(199) = 163. f(163) < f(99) = 162. So no mater which x you choose after several times of f(x),it finally fall in the range of [1,162] and can never get out.2.I check every unhappy number in range of [1,162] , they all fall in loop {4,16,37,58,89,145,42,20} ,which means every unhappy number fall in this loop.其实通过枚举就应该知道上述<=810范围内的数字都会落在特定范围，通过不断缩小范围来找规律。=》
Using fact all numbers in [2, 6] are not happy (and all not happy numbers end on a cycle that hits this interval):
bool isHappy(int n) { while(n>6){ int next = 0; while(n){next+=(n%10)*(n%10); n/=10;} n = next; } return n==1; }
class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ def sum2(num): ans = 0 while num != 0: ans += (num % 10)**2 num = num/10 return ans while n > 6: n = sum2(n) return n == 1
