# 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

| Item | Meaning |
|---|---|
| Input | A positive integer `n` |
| Output | `True` if `n` is happy, otherwise `False` |
| Main operation | Replace `n` by the sum of the squares of its digits |
| Stop condition | Reach `1` or repeat a previous number |

Example function shape:

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

## Examples

Example 1:

```python
n = 19
```

Apply the process:

```text
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:

```python
True
```

Example 2:

```python
n = 2
```

Apply the process:

```text
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:

```python
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`:

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

Implementation:

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

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

    return total
```

The line:

```python
digit = n % 10
```

gets the last digit.

The line:

```python
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:

```python
n = 19
```

Initial state:

```python
seen = set()
```

First iteration:

```text
n = 19
seen = {}
next = 82
```

Second iteration:

```text
n = 82
seen = {19}
next = 68
```

Third iteration:

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

Fourth iteration:

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

Now `n == 1`.

Return:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(k log n)` | Each transformation scans the digits, and `k` transformations occur before reaching `1` or a cycle |
| Space | `O(k)` | The set stores previously seen values |

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:

```text
10 digits * 9^2 = 810
```

After that, the sequence stays small.

## Implementation

```python
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:

```python
seen = set()
```

The loop continues until `n` becomes `1`:

```python
while n != 1:
```

If `n` already appeared, we found a cycle:

```python
if n in seen:
    return False
```

Otherwise, we record the current value:

```python
seen.add(n)
```

Then we move to the next value in the sequence:

```python
n = self.next_number(n)
```

The helper function extracts digits one by one:

```python
digit = n % 10
```

Then it adds the square of that digit:

```python
total += digit * digit
```

Finally, it removes the last digit:

```python
n //= 10
```

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

```python
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:

```text
19 -> 82 -> 68 -> 100 -> 1
```

Use two runners:

| Pointer | Movement |
|---|---|
| `slow` | Moves one step |
| `fast` | Moves two steps |

If the sequence reaches `1`, return `True`.

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

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `19` | Standard happy example |
| `2` | Standard unhappy example |
| `1` | Already happy |
| `7` | Reaches `1` after several steps |
| `4` | Enters the known unhappy cycle |
| `100` | Contains zeros and reaches `1` |