Skip to content

Volume ITechnology

4.28.4 — Happy Number ​

LeetCode 202 · Easy

The problem ​

Repeatedly replace a number by the sum of the squares of its digits. It is happy if this eventually reaches 1, and unhappy if it loops forever.

19  →  1²+9² = 82  →  8²+2² = 68  →  6²+8² = 100  →  1²+0²+0² = 1   →  true
2   →  4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → …               →  false

The pattern ​

The process is deterministic: each number has exactly one successor. So the sequence either reaches 1 or repeats a value it has already visited — and once it repeats, it is in a cycle forever.

That is 4.9.7 Linked List Cycle with next(n) = the digit-square sum. Any process with a single successor is a linked list, whether or not there are any pointers involved.

Two ways to detect the repeat:

  • A set of everything seen. Simple, O(\log n) space.
  • Floyd's slow and fast pointers. O(1) space, and the reason this problem is filed where it is.

The digit-square step ​

python
def next_number(n: int) -> int:
    total = 0
    while n:
        n, digit = divmod(n, 10)
        total += digit * digit
    return total

divmod(n, 10) peels the last digit and shifts the rest down in one call. This loop is the standard way to walk a number's digits and it appears in half the problems in this chapter.

The solution ​

python
class Solution:
    def isHappy(self, n: int) -> bool:
        def next_number(x: int) -> int:  # (1)
            total = 0
            while x:
                x, digit = divmod(x, 10)  # (2)
                total += digit * digit  # (3)
            return total

        slow, fast = n, next_number(n)  # (4)

        while fast != 1 and slow != fast:  # (5)
            slow = next_number(slow)  # (6)
            fast = next_number(next_number(fast))  # (7)

        return fast == 1  # (8)
ts
function isHappy(n: number): boolean {
  const next = (x: number): number => {  // (1)
    let total = 0;
    while (x > 0) {
      const d = x % 10;  // (2)
      total += d * d;  // (3)
      x = Math.floor(x / 10);
    }
    return total;
  };

  let slow = n, fast = next(n);  // (4)

  while (fast !== 1 && slow !== fast) {  // (5)
    slow = next(slow);  // (6)
    fast = next(next(fast));  // (7)
  }

  return fast === 1;  // (8)
}

Line by line ​

(1) next_number replaces a number with the sum of the squares of its digits.

(2) Peel off the last digit. divmod(x, 10) gives two answers at once: x with its last digit removed, and that last digit. For 19 it gives 1 and 9. TypeScript does the same with % 10 for the digit and Math.floor(x / 10) for the rest.

(3) Add the digit's square.

(4) Two pointers walk the chain of numbers, exactly like 4.9.7 Linked List Cycle. Each number has exactly one next number, so the numbers form a chain. fast starts one step ahead.

(5) Stop when fast reaches 1, or when the two pointers meet. Meeting means the chain has looped round without passing 1.

(6) slow moves one step, and

(7) fast moves two steps.

(8) Happy exactly when the chain reached 1. Note that 1 leads to itself, because 1^2 = 1. So a happy chain also ends in a loop, the loop of just 1. That is why checking fast == 1 is enough.

Trace ​

Take n = 19. The chain is 19 → 82 → 68 → 100 → 1, because 1 + 81 = 82, 64 + 4 = 68, 36 + 64 = 100 and 1 + 0 + 0 = 1.

Stepslowfast
start1982
182100 (82 → 68 → 100)
2681 (100 → 1 → 1)

fast is 1, so 19 is happy.

The loop ends for one of two reasons, and the return distinguishes them: fast == 1 means happy; slow == fast with fast != 1 means a cycle.

fast starts one step ahead, so the equality test does not fire immediately on the first iteration.

Only fast is checked against 1. It moves faster, so it reaches 1 first if 1 is reachable at all.

The set version ​

python
def isHappy(self, n):
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = next_number(n)
    return n == 1

Shorter, easier to read, O(\log n) space. Write this first, then offer Floyd's when asked about space.

Why the sequence cannot run away to infinity ​

It also explains why the process always stops instead of running forever.

For a three-digit number the largest possible digit-square sum is 9^2 \times 3 = 243. For any number with four or more digits the sum is smaller than the number itself — a four-digit number is at least 1,000 while its sum is at most 324.

So every sequence drops below 1,000 within a few steps and stays there. With a finite set of reachable values and a deterministic step, the sequence must eventually repeat. It cannot escape upwards.

In fact every unhappy number falls into the same single cycle: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. So a valid solution is to check whether the sequence ever hits 4. It works, and it relies on a fact you would have to look up — mention it as a curiosity, not as your answer.

Edge cases ​

  • n = 1. Already happy. The loop never runs.
  • An unhappy number, like 2. Its chain falls into the loop 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4, which never reaches 1. The pointers meet inside it.

Complexity ​

O(\log n) time for the first step — the number of digits — and then a bounded number of steps, since values quickly fall below 1,000.

O(1) space with Floyd's; O(\log n) with the set.

Where this goes next ​

The technique — treat a deterministic process as a linked list and use cycle detection — is the transferable part:

  • Linked List Cycle — the original. 4.9.7.
  • Find the Duplicate Number — an array read as a function from index to index. 4.9.8.
  • Pseudorandom number generators — Floyd's is how you measure a generator's period, and a short period is a real defect.
  • Detecting infinite loops in a state machine — the same test.

What the interviewer will push on ​

"How do you know it terminates?" Values above 1,000 shrink, so the sequence is confined to a finite set and must repeat.

"Why does cycle detection apply?" Each number has exactly one successor, which is a linked list.

"Can you do it in O(1) space?" Floyd's slow and fast.

"Why check only fast against 1?" It moves faster, so it arrives first.

"Is there a shortcut?" Every unhappy number reaches 4. Say it is a looked-up fact rather than a derivation.

One thing to volunteer: say "this is a linked list without pointers" before writing anything. It turns an arithmetic puzzle into a problem you have already solved, and that is what pattern recognition is for.

Next: 4.28.5 Plus One — the shortest problem in the chapter, with exactly one interesting input.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet