202.md

202. Happy Number

Description

A happy number is number defined by the following process: starting with any positive integer, repalce the number by the sum of the squares of its digits, and repeat the process until the number equals 1, or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Thinking Process

1. Approach 1, use a hash set to store the results of each iteration. If number 1 is spotted, return true. Otherwise keep iterating until the set discovers a duplicate. Return false if the duplicate is not 1.
2. Approach 2, use two pointers technique, have two instances of the iteration. One iterates one step at a time, the other iterates two step at a time. They will eventually meet.

Code

Approach 1

public class Solution {
    public boolean isHappy(int n) {       
        Set<Integer> set = new HashSet<>(); 
        while(!set.contains(1)){
            if(n == 1)
                return true;
            if(!set.add(n))
                return false;
            n = nextIteration(n);
        }
        return true;
    }
    
    int nextIteration(int n){
        int nextN = 0;
        while(n != 0){
            nextN += (n % 10) * (n % 10);
            n /= 10;
        }
        return nextN;
    }
}

Approach 2

public class Solution {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = n;
        do{
            if(slow == 1 || fast == 1)
                return true;
            slow = nextIteration(slow);
            fast = nextIteration(nextIteration(fast));
        }while(slow != fast);
        return slow == 1;
    }
    int nextIteration(int n){
        int nextN = 0;
        while(n != 0){
            nextN += (n % 10) * (n % 10);
            n /= 10;
        }
        return nextN;
    }
}

Complexity

1. Approach 1 has a space complexity of O(n)
2. Approach 2 has a space complexity of O(1)
3. Time complexity is not quantifiable