Happy Number Detection Algorithm using Hash Set

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

Happy Number Detection Algorithm using Hash Set

The difficult part is how to detect the loop. If you don’t detect the loop, then the program will never end for example,

3, 9, 81, 65, 61, 37, 58, 33, 18, 65 …

Luckily, we have various STL data structures that can help remember the past. The set structure is most suitable.

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

class Solution {
public:
    int getNumber(int n) {
        int r = 0;
        while (n > 0) {
            int p = n % 10;
            r += p * p;
            n /= 10;
        }
        return r;
    }
 
    bool isHappy(int n) {
        unordered_set<int> ban;
        while (n != 1) {
            int x = getNumber(n);
            if (ban.count(x)) { // in the ban list
                return false;
            }
            n = x;
            ban.insert(x); // add this number to the ban list
        }
        return true;
    }
};

class Solution {
public:
    int getNumber(int n) {
        int r = 0;
        while (n > 0) {
            int p = n % 10;
            r += p * p;
            n /= 10;
        }
        return r;
    }

    bool isHappy(int n) {
        unordered_set<int> ban;
        while (n != 1) {
            int x = getNumber(n);
            if (ban.count(x)) { // in the ban list
                return false;
            }
            n = x;
            ban.insert(x); // add this number to the ban list
        }
        return true;
    }
};

How can you prove that the above will detect the duplication? The number of digits for n is log10(n) and if the maximum square sum for log10(n) digits are 81*log10(n) and therefore, this is the maximum number of iterations (in theory) before the function returns.

Of course, this could be done in recursive manner:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    bool isHappy(int n) {
        if (n == 1) return true;
        if (data.count(n)) return false;
        data.insert(n);
        int r = 0;
        while (n > 0) {
            r += (n % 10) * (n % 10);
            n /= 10;
        }
        return isHappy(r);
    }
private:
    unordered_set<int> data;
};

class Solution {
public:
    bool isHappy(int n) {
        if (n == 1) return true;
        if (data.count(n)) return false;
        data.insert(n);
        int r = 0;
        while (n > 0) {
            r += (n % 10) * (n % 10);
            n /= 10;
        }
        return isHappy(r);
    }
private:
    unordered_set<int> data;
};

See also: Teaching Kids Programming – Algorithms to Determine a Happy Number

–EOF (The Ultimate Computing & Technology Blog) —