Happy Number — InterviewPrepKit

Solving tips

The process either reaches 1 or falls into a cycle, so this is really cycle detection on the sequence x -> sum of squares of digits.
Simplest: keep a set of seen values; exit True when you hit 1, False when you revisit a value.
For O(1) space, apply Floyd's tortoise-and-hare (slow one step, fast two steps) treating next_num as the 'next' pointer; start fast one step ahead.
Compute sum of SQUARES of digits (a common slip is summing the digits); values quickly bound below 243, so runtime is effectively O(log n).

Problem

Define one step on a positive integer as: replace the number by the sum of the squares of its digits. A number is happy if repeatedly applying this step eventually reaches 1. If the process instead falls into a loop that never contains 1, the number is not happy. Given n, return True if it is happy, otherwise False.

Examples

n = 19 → True — 19 → 1²+9²=82 → 8²+2²=68 → 6²+8²=100 → 1²+0²+0²=1.
n = 2 → False — the sequence 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ... cycles back to 4 without ever hitting 1.
n = 7 → True — 7 → 49 → 97 → 130 → 10 → 1.

Constraints

1 <= n <= 2^31 - 1

Think about it first

Hint 1

The process either reaches 1 or runs forever. Running forever means it must eventually revisit a number it has already seen — a cycle. So detecting a repeat is the whole game.

Hint 2

Store every number you have already produced in a set. If you ever generate a number already in the set (and it isn't 1), you're in a cycle and the answer is `False`.

Hint 3

This is a "does the sequence terminate or cycle" question — exactly what Floyd's tortoise-and-hare does with O(1) extra memory. Run a slow pointer one step and a fast pointer two steps; if they meet at 1, happy; if they meet elsewhere, it's a loop.

TL;DR

Iterate the digit-square-sum step and detect a cycle — with a hash set (O(log n) time/space) or Floyd’s cycle detection (O(1) space).

Approach 1 — Cycle detection with a hash set

The insight: the sequence is fully determined by the current value, so if a value ever repeats, everything after it repeats forever. Remember every value seen; stop when you reach 1 (happy) or revisit a value (not happy).

class Solution:
    def isHappy(self, n: int) -> bool:
        def next_num(x: int) -> int:
            total = 0
            while x:
                x, d = divmod(x, 10)
                total += d * d
            return total

        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = next_num(n)
        return n == 1

Walkthrough with n = 19: 19 → 82 → 68 → 100 → 1. No repeat before reaching 1, so the loop exits with n == 1 → True. For n = 2: the sequence eventually produces 4 a second time; at that point n in seen, the loop exits with n != 1 → False.

Complexity: O(log n) digits per step, and the values quickly drop below 243 (the max digit-square-sum for any number under 1000), so the sequence length before repeating is bounded by a constant. Effectively O(log n) time, O(log n) space for the set.

Approach 2 — Floyd’s tortoise and hare (O(1) space)

The insight: “reaches 1 or cycles” is structurally identical to “does a linked list have a cycle,” where next_num is the next pointer. Floyd’s algorithm walks a slow pointer one step and a fast pointer two steps per iteration; if there is a cycle they eventually land on the same value, and if the sequence terminates the fast pointer reaches the fixed point 1 (since next_num(1) == 1).

class Solution:
    def isHappy(self, n: int) -> bool:
        def next_num(x: int) -> int:
            total = 0
            while x:
                x, d = divmod(x, 10)
                total += d * d
            return total

        slow = n
        fast = next_num(n)
        while fast != 1 and slow != fast:
            slow = next_num(slow)
            fast = next_num(next_num(fast))
        return fast == 1

Walkthrough with n = 2: slow follows 2, 4, 16, 37, ... and fast runs twice as fast through 4, 16, 58, 145, .... Because the 4 → ... → 4 loop is closed, the two pointers eventually coincide on some value that is not 1, so fast != 1 and we return False. With n = 19, fast reaches 1 first, the loop condition fast != 1 breaks, and we return True.

Complexity: O(log n) time (same bounded iteration count, constant work per step aside from digit processing), O(1) space — no set required.

Common pitfalls

Recomputing the digit-square-sum incorrectly, e.g. summing digits instead of squares of digits.
Forgetting that 1 is the target: with the set version you must test n == 1 as the success exit, not just “no repeat.”
In Floyd’s version, initializing slow and fast to the same value and checking equality before advancing — the loop would exit immediately. Start fast one step ahead.

Pattern takeaway

A deterministic sequence x → f(x) on a finite (or eventually bounded) domain must either hit a fixed target or enter a cycle. Detect the cycle either by memorizing visited states (hash set) or, for O(1) space, by Floyd’s tortoise-and-hare — the same trick used for cycle detection in linked lists.