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:

Input: 19 Output: true Explanation: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

Solution: Using Hash Table

We save the sum in a hash table, once we found a loop, we break the while loop.

bool isHappy(int n) {
    // write your code here
    unordered_map<int, bool> m;
    while (true) {
        int sum = 0;
         while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }

        n = sum;
        if (m[sum]) {
            break;
        } else {
            m[sum] = true;
        }
    }
    return n == 1;
}

Solution: Using fast and slow pointer

This problem is similar to detecting cycle in linked list, where we use one fast pointer and one slow pointer. One moves forward one step at a time, one moves forward two steps a time. If there's a cycle then fast and slow will eventually meet each other.

int squareSum(int n) {
    int sum = 0;
    while (n) {
        sum += pow(n%10, 2);
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) {
    // write your code here
    int slow = n, fast = n;
    while (true) {
        slow = squareSum(slow);
        fast = squareSum(fast);
        fast = squareSum(fast);
        if (slow == fast) break;
        else if (fast == 1) break;
    }
    return fast == 1;
}