202. Happy Number

Problem¶

Given a positive integer n, repeatedly replace it with the sum of the squares of its digits.

• Return True if this process eventually reaches 1.
• Return False if it falls into a cycle that never reaches 1.

n = 19
19 -> 1^2 + 9^2 = 82 -> 8^2 + 2^2 = 68 -> 6^2 + 8^2 = 100 -> 1
result = True

Key trick¶

Use cycle detection.

• Store seen values in a set.
• Recompute the digit-square sum until either:
  • you reach 1, or
  • you see a repeated number, which means a loop.

Trap¶

• Forgetting that the process can cycle forever.
• Reusing n while extracting digits and accidentally losing the original state logic.
• Missing the fact that 1 is the only successful terminal state.
• Using string conversion works, but a digit loop is usually cleaner in interviews.

Why is it interesting?¶

It looks like a math problem, but the real idea is detecting repeated state in a process. It tests clean simulation, cycle detection, and reasoning about termination.

Python solution¶

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

        while n != 1 and n not in seen:
            seen.add(n)
            total = 0

            while n > 0:
                n, digit = divmod(n, 10)
                total += digit * digit

            n = total

        return n == 1

Comment on my solution¶

Your solution is correct.

• The set-based cycle detection is the right approach.
• The implementation is a bit less clean because n is reused inside the digit loop, which makes the control flow harder to read.
• A small improvement is to keep the old value in a temporary variable or just compute into total, as in the solution above.
• The comment about x^2 + y^2 + z^2 = 10^k is not needed and does not help solve the problem.

## Solution

class Solution:
    def isHappy(self, n: int) -> bool:
        # x^2 + y^2 + z^2 = 10^k
        # - it loops endlessly in a cycle which does not include 1
        #   - I don't see why this would happens, but let assume it
        #     is true, so a map keep track of computed n will do the trick

        seen = set()
        while True:
            m = 0
            while n != 0:
                n, d = divmod(n, 10)
                m += d**2
            n = m
            if n == 1:
                return True
            if n in seen:
                # We are looping
                return False
            else:
                seen.add(n)

Extra¶

Why the algo terminates?¶

Explain and demonstrate (preferably mathematicaly) why this algorithm has two final state: n is 1 or there's a cycle.

Let

The algorithm repeatedly applies \(f\).

Why only two possible endings?¶

There are only two ways a repeated deterministic process can behave:

• It reaches a fixed point
• It eventually repeats a previous state, which creates a cycle

Since the next value is fully determined by the current value, if the same number appears twice, the rest of the sequence will repeat forever from there.

So the real question is: can the process keep producing new numbers forever without repeating?

The key mathematical fact¶

For any number with \(k\) digits,

because each digit is at most 9.

That means:

• if \(n\) has many digits, \(f(n)\) is much smaller than \(n\)
• the sequence quickly drops into a bounded range

I see what's happening, but I don't fully get it. Anyway, it's enough for now.

Why that forces either 1 or a cycle¶

Once the sequence is inside a finite set, keep applying \(f\):

• there are only finitely many possible values
• if the sequence never repeats, it would need infinitely many distinct values
• that is impossible in a finite set

So repetition must happen.

And repetition means a cycle.

Why 1 is special¶

So 1 is a fixed point, which is a cycle of length 1.

That gives the two outcomes:

• reach 1 and stay there
• repeat some other values forever in a cycle

Example of a non-happy cycle¶

Starting from 2:

It repeats 4, so it cycles forever and never reaches 1.

Small extra insight¶

This also explains why a set works:

• if you see a number again, you have entered a cycle
• if you see 1, you are done immediately

So the algorithm is really detecting the only two possible terminal behaviors of a deterministic process on a finite reachable state space.

Mathematical proof of algo termination¶

Ok I almost get it.

But I no longer want "approximate" explanations like "That means the number of digits eventually drops." and "Once the number has only a few digits, it belongs to a finite set of possibilities.".

In mathematics, we prove we don't explain. I want a proof, like for a given number m there's an upper bound M such that applying f repeatedly is below such M. I want the proof of such M (constructively or reasonning by absurd).

Do you get it?

Goal¶

We want a concrete bound showing that repeated application of

must eventually stay below some fixed number.

A clean proof¶

Let \(n\) have \(k\) digits. Then

because each digit contributes at most \(9^2=81\).

Now choose a number with at least 4 digits. For any \(k \ge 4\),

So if \(n\) has \(k \ge 4\) digits, then \(f(n) < 10^{k-1}\), which means \(f(n)\) has at most \(k-1\) digits.

So every time the number has at least 4 digits, the next value has fewer digits.

Therefore, after finitely many steps, the process reaches a number with at most 3 digits.

Fixed bound¶

If a number has at most 3 digits, then

So after finitely many steps, all iterates are in the finite set

That is the explicit bound you asked for.

Conclusion¶

Once the sequence is inside \(\{1,\dots,243\}\):

• if it reaches \(1\), we are done
• otherwise, since there are only finitely many values, some value must repeat
• repetition implies a cycle

So the process must end in either \(1\) or a cycle.

Even more explicit¶

For any starting value \(n\), there exists \(t\) such that

where \(f^{(t)}\) means applying \(f\) \(t\) times.

That is the constructive bound.

Additional proof¶

We prove by induction on \(k \ge 4\) that

Base case¶

For \(k=4\),

So the claim holds for \(k=4\).

Inductive step¶

Assume for some \(k \ge 4\) that

We want to prove

Since \(k \ge 4\),

And because \(k \ge 4\),

A cleaner way is to use the stronger fact:

So it is enough to know that

which is true because \(2<10\).

Thus,

So the claim holds for \(k+1\).

Therefore, by induction,

Shorter direct proof¶

For \(k \ge 4\),

and

is false as written, so this route is not the right one.

The cleanest direct observation is:

• the function \(10^{k-1}/k\) grows very fast
• checking the first case \(k=4\) is enough to see the exponential dominates the linear term

But if you want a formal proof, induction above is the standard one.

Very simple induction, corrected¶

From the inductive hypothesis,

then

because \(2<10\).

That completes the proof.