Leetcode 202. Happy Number - Important interview question explained step by step

In this article, we’ll discuss an efficient Java solution to check whether a number is a Happy Number. A number is called happy if, by repeatedly replacing it with the sum of the squares of its digits, it eventually equals 1. If a number enters a loop that does not include 1, it’s called an unhappy number.

Problem Breakdown

A happy number follows this process:

Start with any positive integer.
Replace the number with the sum of the squares of its digits.
Repeat the process until the number becomes 1, indicating the number is happy. If a cycle is detected, the number is not happy.

Java Solution: Code and Explanation

We’ll implement this solution in two parts:

A helper function to calculate the sum of the squares of the digits.
The main function that uses a set to detect cycles, ensuring no infinite loops.

Code Implementation:

private static int getSumOfSquareOfNumberDigits(int num) {
	    int sum = 0;

	    while (num > 0) {
	        int digit = num % 10;
	        num /= 10;
	        sum += digit * digit;
	    }
	    return sum;
	}

	private static boolean isHappyNumber(int n) {
	    if (n <= 0) return false; // Adding check for negative and zero cases

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

	    while (n != 1 && seen.add(n)) {
	        n = getSumOfSquareOfNumberDigits(n);
	    }

	    return n == 1;
	}

Explanation

Helper Function (getSumOfSquareOfNumberDigits): This method calculates the sum of the squares of the digits of the input number.
- Example: For 19, it will return 1² + 9² = 1 + 81 = 82.
Main Function (isHappyNumber): This function checks if the number is happy.
- We use a Set to store previously seen sums, ensuring that if the number enters a cycle, we can detect it.
- The loop continues until the number becomes 1 (happy number) or we detect a cycle.

Key Points:

Edge Cases: We return false for 0 and negative numbers since they aren’t considered happy numbers.
Cycle Detection: The use of a Set allows us to efficiently detect cycles.

Time and Space Complexity

Time Complexity: O(log n) for each iteration, where n is the current number, because we are working with the digits of the number.
Space Complexity: O(log n) for the Set that stores the previously seen sums.

Conclusion

This simple approach efficiently checks if a number is happy by breaking it down into smaller operations. Using Java's HashSet, we handle cycles and ensure the algorithm doesn’t run indefinitely.

#Happy Number in Java #Java Happy Number Algorithm #Sum of Squares of Digits #Cycle Detection in Numbers