Leetcode — 202. Happy Number

The link to the problem: https://leetcode.com/problems/happy-number/

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.
• 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.

Return true if n is a happy number, and false if not.

Example 
Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² 

Thoughts:

From reading the definition of the happy number, it is kind of straightforward to write the code of calculating the sum of the squares of the given number’s digits. We can just use a loop and use modulo and division to help us get the current last digit (n mod 10) and abandon the last digit (n divided by 10).

For example, if we have a number like 123, then 123 mod 10 will help us get the last digit, and 123 divided by 10 will help us get rid of the last digit.

Hence, we can use the below helper method to find the number that is going to be our new n:

public int helper(int n){
        int sum = 0;
        while(n>0)
        {
            int lastDigit = n%10;
            sum += lastDigit*lastDigit;
            n/=10; //abandon the last digit
        }
        return sum;
    }

and we will keep calling this helper method by passing n until n is 1 OR until we found that we are in a cycle.

So the biggest question is, how can we find a cycle if there’s one?

The easiest way to do it is by using a set to store all the numbers we have seen before. Once we found we have passed the number into the helper method before, it means that’s the start of the cycle and we can just return false since we already know using that number won’t help us find 1.

Below is the 1ms code that beats 84% — (the details of the helper method is above)

public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while(n>0)
        {
            n = helper(n);
            if(n==1)
                return true;
            if(set.contains(n))
                return false;
            set.add(n);
        }
        return false;
    }

If you have practiced 141. Linked List Cycle before, you might find that the idea of this question is actually surprisingly similar! Yes, we can also use “two pointers — slow pointer and fast pointer” to help us find a cycle.

1. slow — represents the result of calling the helper method one time at a time.
2. fast — represents the result of calling the helper method twice at a time.

We will find there’s a cycle if slow and fast get the same result.

Below is the 0ms code that beats 100% — (the details of the helper method is above)

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