Module 3 · Fast & Slow Pointer

Happy Number

EasyProblem 7 of 17 8 min read ~15 min to solve LeetCode

Linked ListTwo PointersFast SlowMathCycle Detection

Asked atAmazonGoogleMicrosoftAdobeBloomberg

Problem Statement

Write an algorithm to determine whether a positive integer n is a happy number.

Starting with n, replace the number by the sum of the squares of its digits. Repeat the process. If the sequence eventually reaches 1, the number is happy. If it loops forever without reaching 1, the number is not happy.

Input

A positive integer n.

Output

A boolean: true if repeated digit-square-sum transformation reaches 1, otherwise false.

Constraints

•1 <= n <= 2^31 - 1

Examples

Example 1

Input:

n = 19

Output: true

Explanation: The sequence is **19 -> 82 -> 68 -> 100 -> 1**, so it reaches 1.

Example 2

Input:

n = 2

Output: false

Explanation: The sequence enters **4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4**, so it cycles without reaching 1.

Learning Objectives

Reframe a numeric sequence as an implicit linked list.
Apply fast and slow cycle detection without materializing nodes.
Distinguish the success terminal state **1** from a non-happy cycle.
Implement the digit-square-sum transition safely for positive integers.

Intuition

Pattern Recognition

This belongs in a linked-list module because the repeated transformation creates an implicit linked list. Each number is a node, and its next pointer is the sum of the squares of its digits. The list is not stored in memory, but the one-next structure is real.

From any starting number, the sequence either reaches 1 or eventually repeats a previous number. A repeat means the implicit list has a cycle. Instead of keeping a set of seen numbers, run slow through one transformation and fast through two transformations. If fast reaches 1, the number is happy. If slow and fast meet somewhere else, the sequence is trapped in a cycle.

Common mistakes

×Treating the problem as pure math and missing the implicit linked-list cycle pattern.
×Returning false as soon as a value decreases or increases; the sequence is not monotonic.
×Checking only whether **slow** reaches 1 while **fast** may have already reached 1.
×Writing digit extraction that accidentally ignores the final digit.

Algorithm Explanation

Key idea

Define next(number) as the sum of squared digits. This gives every positive integer exactly one outgoing edge, just like a linked-list node has one next pointer. Floyd's algorithm can detect whether the generated path reaches 1 or falls into a cycle.

Pointer walkthrough

For 19, the implicit list is 19 -> 82 -> 68 -> 100 -> 1. Start slow at 19 and fast at 82. After one loop, slow moves to 82 while fast jumps from 82 to 100. After another loop, slow moves to 68 while fast reaches 1. The terminal value wins, so 19 is happy.

For 2, the path eventually becomes 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4. In that loop, fast eventually catches slow, proving the sequence will never reach 1.

Algorithm

Set slow = n and fast = next(n).
While fast is not 1 and slow is not equal to fast, move slow once and fast twice.
If fast becomes 1, return true.
If slow equals fast, return false because a non-1 cycle was found.
Implement next by repeatedly taking the last digit, adding its square, and removing that digit.

Solutions

Solution: Floyd cycle detection on digit sums

Model each generated number as a node in an implicit linked list. The helper computes the next node. Floyd's two-speed traversal distinguishes reaching the terminal node 1 from entering a repeated cycle.

Step-by-step

Initialise slow at n and fast at the first transformed value.
Repeat while fast is not 1 and the pointers have not met.
Advance slow by one digit-square-sum transformation.
Advance fast by two transformations.
Return whether fast reached 1.

Time

O(log n)

Space

O(1)

Each transformation processes the digits of the current number, and the sequence quickly enters a bounded set of values.

Java implementation

Loading…

Dry Run

Sample input

n = 2. Track the generated implicit list until the two pointers meet inside the non-happy cycle.

step	slow	fast	signal
start	2	4	fast is not 1 and pointers differ
1	4	37	continue
2	16	89	continue
3	37	42	continue
4	58	4	continue
5	89	37	continue
6	145	89	continue
7	42	42	pointers meet in a cycle

The meeting at 42 is not the terminal value 1, so the implicit list cycles and 2 is not happy.

Interview Tips

Make the implicit-list framing explicit before coding. Interviewers like this problem because it tests pattern transfer: there are no ListNode objects, but every state has exactly one next state. Mention that a hash set is also possible, then explain that fast and slow gives the same cycle detection with constant space.

Likely follow-ups

How would you solve the same problem with a set of seen numbers?
Why does the sequence eventually enter a bounded range even when **n** is large?
How would the transformation change for another base, such as base 2 or base 16?
How would you return the actual cycle values for a non-happy number?

Key Takeaways

An implicit linked list can be defined by a deterministic next-state function.
Happy Number reaches **1**; non-happy numbers enter a cycle that excludes **1**.
Fast and slow pointers work even when nodes are generated on demand.
The helper function is the pointer movement for this problem.

Reusable template: For deterministic repeated transformations, treat each value as a node and run fast and slow on the next-state function to detect a terminal value or cycle.