LeetCode 202: Happy Number

Problem Restatement

We are given a positive integer n.

We repeatedly replace n with the sum of the squares of its digits.

If this process eventually reaches 1, then n is a happy number.

If the process enters a cycle that never reaches 1, then n is not a happy number.

Return True if n is happy. Otherwise, return False.

The official problem defines the process this way: start with any positive integer, replace it by the sum of the squares of its digits, and repeat until it reaches 1 or loops forever in a cycle without 1. Return whether the number is happy.

Input and Output

Example function shape:

def isHappy(n: int) -> bool:
    ...

Examples

Example 1:

n = 19

Apply the process:

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

The process reaches 1, so the answer is:

True

Example 2:

n = 2

Apply the process:

2^2 = 4
4^2 = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 4

Now 4 appears again.

Once a number repeats, the same sequence will repeat forever. Since 1 was not reached, the answer is:

False

First Thought: Simulate the Process

The problem directly describes a process, so the first idea is to simulate it.

For each current number:

1. Split it into digits.
2. Square each digit.
3. Add the squares.
4. Replace the current number with that sum.

The missing detail is when to stop.

If the number becomes 1, we return True.

If a number appears twice, we are in a cycle, so we return False.

Key Insight

This problem is cycle detection.

The sequence either reaches 1 or eventually repeats a previous value.

A repeated value proves that the process has entered a loop, because the next value depends only on the current value.

So we keep a set of numbers we have already seen.

If we see the same number again before reaching 1, the number is not happy.

Helper Function

We need a function that computes the next value.

For example, for n = 82:

8^2 + 2^2 = 64 + 4 = 68

Implementation:

def next_number(n: int) -> int:
    total = 0

    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10

    return total

The line:

digit = n % 10

gets the last digit.

The line:

n //= 10

removes the last digit.

Algorithm

Use a set called seen.

While n is not 1:

1. If n is already in seen, return False.
2. Add n to seen.
3. Replace n with the sum of the squares of its digits.

If the loop ends, then n == 1, so return True.

Walkthrough

Use:

n = 19

Initial state:

seen = set()

First iteration:

n = 19
seen = {}
next = 82

Second iteration:

n = 82
seen = {19}
next = 68

Third iteration:

n = 68
seen = {19, 82}
next = 100

Fourth iteration:

n = 100
seen = {19, 82, 68}
next = 1

Now n == 1.

Return:

True

Correctness

At every step, the algorithm computes exactly the transformation described in the problem: replace the current number with the sum of the squares of its digits.

If the algorithm reaches 1, then by definition the original number is happy, so returning True is correct.

If the algorithm sees a number that already appeared before, the future sequence must repeat from that number onward. The transformation is deterministic, meaning the same input always produces the same next value. Therefore, after a repeated number appears, the process is trapped in a cycle.

Since the algorithm checks for 1 before continuing, a detected cycle cannot contain 1. Returning False is correct.

The problem says every non-happy number loops endlessly in a cycle without 1, so these two cases cover all possible outcomes.

Complexity

For normal LeetCode constraints, this behaves as constant time in practice because numbers quickly shrink into a small range.

For a 32-bit integer, the largest digit-square sum after one step is bounded by:

10 digits * 9^2 = 810

After that, the sequence stays small.

Implementation

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()

        while n != 1:
            if n in seen:
                return False

            seen.add(n)
            n = self.next_number(n)

        return True

    def next_number(self, n: int) -> int:
        total = 0

        while n > 0:
            digit = n % 10
            total += digit * digit
            n //= 10

        return total

Code Explanation

We store previous values here:

seen = set()

The loop continues until n becomes 1:

while n != 1:

If n already appeared, we found a cycle:

if n in seen:
    return False

Otherwise, we record the current value:

seen.add(n)

Then we move to the next value in the sequence:

n = self.next_number(n)

The helper function extracts digits one by one:

digit = n % 10

Then it adds the square of that digit:

total += digit * digit

Finally, it removes the last digit:

n //= 10

When the loop exits, n == 1, so the number is happy:

return True

Alternative: Fast and Slow Pointers

We can also solve this without a set using Floyd’s cycle detection.

Think of each number as pointing to the next number.

For example:

19 -> 82 -> 68 -> 100 -> 1

Use two runners:

If the sequence reaches 1, return True.

If slow and fast meet before reaching 1, there is a cycle, so return False.

class Solution:
    def isHappy(self, n: int) -> bool:
        slow = n
        fast = self.next_number(n)

        while fast != 1 and slow != fast:
            slow = self.next_number(slow)
            fast = self.next_number(self.next_number(fast))

        return fast == 1

    def next_number(self, n: int) -> int:
        total = 0

        while n > 0:
            digit = n % 10
            total += digit * digit
            n //= 10

        return total

The set version is usually easier to read. The fast and slow pointer version uses O(1) extra space.

Testing

def run_tests():
    s = Solution()

    assert s.isHappy(19) is True
    assert s.isHappy(2) is False
    assert s.isHappy(1) is True
    assert s.isHappy(7) is True
    assert s.isHappy(4) is False
    assert s.isHappy(100) is True

    print("all tests passed")

run_tests()