202. Happy Number

三刷 06/2022

Version #1 HashSet

Time O(logN)

Space O(logN)

Runtime: 3 ms, faster than 43.67% of Java online submissions for Happy Number.

Memory Usage: 41.4 MB, less than 38.37% of Java online submissions for Happy Number.

class Solution {

    public boolean isHappy(int n) {

        Set<Integer> visited = new HashSet<>();

        while (n != 1) {

            if (visited.contains(n)) {

                return false;

            }

            visited.add(n);

            int next = 0;

            while (n > 0) {

                next += (n % 10) * (n % 10);

                n /= 10;

            }

            n = next;

        }

        return true;

    }

}

Version #2 Slow fast pointers
"use faster and lower runner solution. (2 pointers)
the faster one move 2 steps, and slower one move only one step. if there's a circle, the faster one will finally "catch" the slower one.   (the distance between these 2 pointers will decrease one every time.)"
O(1) Space

[2ND TRY]
85.28 %
class Solution {
    public boolean isHappy(int n) {
int slow = n, fast = n;
while (fast != 1) {
slow = getNext(slow);
fast = getNext(fast);
if (fast == 1) return true;
fast = getNext(fast); // fast jump two steps
if (slow == fast) return false;
}
return fast == 1;
}

private int getNext(int x) {
int result = 0;
while (x > 0) {
result += (x % 10) * (x % 10);
x /= 10;
}
return result;
}
}

[1ST TRY]
 79.79 %
class Solution {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = n;
        do {
            slow = digitSquareSum(slow);
            fast = digitSquareSum(fast);
            fast = digitSquareSum(fast);
            if (fast == 1) return true;
        } while (slow != fast);
        return false;
    }
    private int digitSquareSum(int n) {
        int sum = 0;
        while (n > 0) {
            sum += (n % 10) * (n % 10);
            n = n / 10;
        }
        return sum;
    }
}


Version #1 Using a hashset to keep track of visited values

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