LeetCode — 202. Happy Number

A happy number is an integer that leads to 1 after a sequence of steps wherein each step involves replacing the number with the sum of the squares of its digits. In this blog post, we’ll discuss a Java method to determine if a given number is a happy number.

The Approach

We use a HashSet to record the sums of the squares of the digits of the numbers encountered during the process. The HashSet is crucial as it helps us identify cycles — if a number reappears, it means we are in a loop and the original number is not a happy number.

The Process

Our isHappy function takes an integer n and utilizes a while loop to calculate the sum of the squares of its digits continuously. The sum is calculated using a helper function, sum, which breaks down the number into individual digits and sums up their squares.

Cycle Detection

As we calculate these sums, each sum is added to the HashSet record. If we encounter a sum that is already in the HashSet, it indicates that we are in a cycle. Since we cannot reach 1 in a cycle, the function then returns false.

Termination Condition

The process either ends when we first get a sum of 1, confirming the number is happy, or when we detect a cycle, confirming the number is not happy.

Time Complexity

The time complexity of the algorithm is O(log n), where n is the input number. This is because the number of digits in a number is proportional to the logarithm of the number, and the algorithm’s runtime primarily depends on the number of digits being processed.

Space Complexity

The space complexity is O(d), where d is the number of distinct sums generated during the process. The HashSet’s size grows with the variety of sums encountered, but this is usually a manageable number.

JavaScript version

/**
 * @param {number} n
 * @return {boolean}
 */
var getSum = function (n) {
    let sum = 0;
    while (n) {
        sum += (n % 10) ** 2;
        n = Math.floor(n / 10);
    }
    return sum;
}

var isHappy = function (n) {
    let set = new Set();
    while (n !== 1 && !set.has(n)) {
        set.add(n);
        n = getSum(n);
    }

    return n === 1;
};

Java version

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();

        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = sum(n);
        }

        return n == 1;
    }

    public int sum(int n) {
        int sum = 0;

        while (n > 0) {
            // To get the last digit of a number
            // find the remainder when it is divided by 10
            int LastDigit = n % 10;
            sum += LastDigit * LastDigit;
            n = n / 10;
        }

        return sum;
    }
}