Leetcode-202-Happy Number

Posted 2022-07-13

5~6 min read

Happy Number

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

Description:

Write an algorithm to determine if a number n 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.
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.

Idea:

solution

Step1: build the get sum method, get the number on each digit of a number by taking the modulo, and divid the original number with 10 to remove the last digit.

Step2: use set to store each sum of n, and make n = sum round by round(or use recursion), until n=1, or there exists same sum in the result

Step3: verify n is 1 or not

Code:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//recursion
class Solution {
    Set<Integer> result = new HashSet<>();
    public boolean isHappy(int n) {
        if(n<=0){
            return false;
        }
        if(n==1){
            return true;
        }
        if(result.contains(n)){
            return false;
        }
        result.add(n);
        n = getSum(n);
        return isHappy(n);
    }
    public int getSum(int n){
        int sum = 0;
        while(n!=0){
            sum += (n%10)*(n%10);
            n=n/10;
        }
        return sum;
    }
}

//non-recursion
class Solution {
    public boolean isHappy(int n) {
        Set<Integer> result = new HashSet<>();
        if(n<=0){
            return false;
        }
        while(n!=1 && !result.contains(n)){
            result.add(n);
            n = getSum(n);
        } 
        return n==1;
    }
    public int getSum(int n){
        int sum = 0;
        while(n > 0){
            sum += (n%10)*(n%10);
            n=n/10;
        }
        return sum;
    }
}

Leetcode

Leetcode Hash