202. Happy Number

Posted on | Edited on | Views:

https://leetcode.com/problems/happy-number/

Approach 1: Detect Cycles with a HashSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    private int getNext(int n){
        int totalSum=0;
        while(n>0){
            int d=n%10;
            n/=10;
            totalSum+=d*d;
        }
        return totalSum;
    }
    public boolean isHappy(int n) {
        Set<Integer> seen=new HashSet<>();
        while(n!=1&&!seen.contains(n)){
            seen.add(n);
            n=getNext(n);
        }
        return n==1;
    }
}

Approach 2: Floyd’s Cycle-Finding Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    private int getNext(int n){
        int totalSum=0;
        while(n>0){
            int d=n%10;
            n/=10;
            totalSum+=d*d;
        }
        return totalSum;
    }
    public boolean isHappy(int n) {
        int slow=n,fast=getNext(n);
        while(fast!=1&&slow!=fast){
            slow=getNext(slow);
            fast=getNext(getNext(fast));
        }
        return fast==1;
    }
}

0%