Happy Number

Problem

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

12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Solution

Two Pointers Solution - Slow and Fast (Floyd's Cycle Detection Algorithm)

public class Solution {

    public boolean isHappy(int n) {
        int slow = n, fast = n;
        do {
            slow = getSum(slow);
            if (slow == 1) return true;
            fast = getSum(fast);
            fast = getSum(fast);
        } while (slow != fast);
        return slow == 1;
    }

    private int getSum(int num) {
        int sum = 0, temp = 0;
        while (num > 0) {
            temp = num % 10;
            sum += temp * temp;
            num /= 10;
        }
        return sum;
    }
}

Hash Table Solution - O(n) time and O(n) space

public class Solution {

    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while (set.add(n)) {
            n = getSum(n);
            if (n == 1) return true;
        }
        return false; // n cannot be 1 because if it's 1 method will return true already 
    }

    private int getSum(int num) {
        int sum = 0, temp = 0;
        while (num > 0) {
            temp = num % 10;
            sum += temp * temp;
            num /= 10;
        }
        return sum;
    }
}

Analysis

This problem uses idea of Floyd's Cycle Detection Algorithm
We use a helper method to get square sum of digits
Then the problem becomes to detect if the sum repeated
If so, we know the number is not happy
Remember Floyd's Cycle Detection Algorithm, which uses two pointers fast and slow to detect cycle(repetition)