Problem Statement

You are given a positive integer n. Replace the number by the sum of the squares of its digits, and repeat the process until:

• It becomes 1 (which means it’s a happy number), or
• It loops endlessly in a cycle (not a happy number).

Return true if n is a happy number. Otherwise, return false.

What is a Happy Number?

A happy number is a number that eventually reaches 1 when you repeatedly replace it by the sum of the squares of its digits.

Example:

Let’s take n = 19:

• 1²+9²=1+81=82
• 8²+2²=64+4=68
• 6²+8²=36+64=100
• 1²+0²+0²=1 → Happy number!

Now take n = 6:

• Eventually, the process falls into a loop and never reaches 1. So, 6 is not a happy number.

Solution 1: Using a HashSet to Detect Loops

Intuition:

To detect if a number is entering a cycle (i.e., we’ve seen it before), we can store previously seen numbers in a HashSet.

import java.util.HashSet;
import java.util.Set;

public class HappyNumber {
    public boolean isHappy(int n) {
        if (n <= 0) return false;

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

        while (n != 1) {
            if (seen.contains(n)) {
                return false; // loop detected
            }
            seen.add(n);
            n = sumOfSquares(n);
        }

        return true;
    }

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

Time & Space Complexity:

• Time: O(log n) per digit sum operation × number of steps
• Space: O(k), where k is the size of the cycle or number of unique intermediate results

Solution 2: Floyd’s Cycle Detection (Fast and Slow Pointers)

Intuition:

Inspired by detecting cycles in linked lists. Use two variables:

• Slow pointer: moves one step at a time
• Fast pointer: moves two steps at a time

If there’s a cycle (i.e., it’s not a happy number), they’ll eventually meet at the same number other than 1.

public class HappyNumber {
    public boolean isHappy(int n) {
        if (n <= 0) return false;

        int slow = n;
        int fast = sumOfSquares(n);

        while (fast != 1 && slow != fast) {
            slow = sumOfSquares(slow);
            fast = sumOfSquares(sumOfSquares(fast));
        }

        return fast == 1;
    }

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

Explaination

Step 1: Handle invalid inputs

if (n <= 0) return false;

Happy numbers are only defined for positive integers, so we immediately return false for non-positive inputs (0 or negative numbers).

Step 2: Initialize two pointers

int slow = n;
int fast = sumOfSquares(n);

• We set slow to the original number n.
• We set fast to the sum of the squares of the digits of n (i.e., one step ahead of slow).

Step 3: Run the cycle detection loop

while (fast != 1 && slow != fast) {
    slow = sumOfSquares(slow);
    fast = sumOfSquares(sumOfSquares(fast));
}

This loop continues until:

• fast == 1 → the number is happy
• slow == fast → a cycle is detected (i.e., the number is not happy)

Here’s what happens:

• slow moves one step at a time (sumOfSquares(slow))
• fast moves two steps at a time (sumOfSquares(sumOfSquares(fast)))

This is exactly like detecting a cycle in a linked list using two pointers: a slow and a fast one.

Time & Space Complexity:

• Time: Same as the previous method
• Space: O(1), constant extra space

---

Edge Cases

• n <= 0 → Return false (not a natural number)
• n == 1 → Return true
• Negative numbers → Not valid happy numbers