Algorithm

LeetCode/Happy Number

Problem Summary

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

Solution

At first I used a hash table (unordered_set in STL) to record the numbers and find loops (see Code 2). But this takes extra space and is slower than Floyd’s cycle-finding algorithm. You can find the definition on Wikipedia (Floyd’s cycle-finding algorithm).

The algorithm works with two “pointers”, A and B. A moves twice faster than B. So if there is any loop, A and B will finally meet. In this problem, 1 leads to 1, so they will meet whether the number is happy or not.

Code 1: With Floyd’s cycle-finding algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    bool isHappy(int n) {
    	if (n <= 0)
    		return false;
        int slow = digit_square(n);
        int fast = digit_square(slow);
        while (slow != fast)
        {
        	slow = digit_square(slow);
            fast = digit_square(digit_square(fast));
        }
        return (slow == 1);
    }
    int digit_square(int n)
    {
        int sum = 0,tmp;
        while (n > 0)
        {
            tmp = n%10;
            sum += tmp*tmp;
            n/=10;
        }
        return sum;
    }
};

Code 2: With hash table

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    bool isHappy(int n) {
    	if (n <= 0)
    		return false;
        unordered_set<int> vis;
        while (true)
        {
        	int sum = 0,tmp;
        	while (n > 0)
        	{
        		tmp = n%10;
        		sum += tmp*tmp;
        		n/=10;
        	}
        	if (sum == 1)
        		return true;
        	if (vis.count(sum))
        		return false;
        	vis.insert(sum);
        	n = sum;
        }
        return false;
    }
};