Abstract / Summary

A number is happy if repeatedly replacing it by the sum of the squares of its digits leads to one.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (4+ million submissions).

Typical patterns to solve this problem:

• Hash Table
• Math
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether a given integer n is a happy number. A happy number is defined by repeatedly replacing the number with the sum of the squares of its decimal digits until the result either becomes 1 (happy) or falls into a repeating cycle that does not include 1 (unhappy). The algorithm employs a hash set to detect cycles and iteratively computes the digit-square sum.

Key Steps

The core logic can be divided into three distinct phases: initialization of the cycle-detection container, the iterative transformation loop, and the digit-square accumulation routine.

Initialization of the Cycle-Detection Container

unordered_set<int> seen;

An unordered set named seen is created to store each intermediate value of n. Because the set provides constant-time lookup, it efficiently supports the detection of previously encountered numbers, which signals the start of a cycle.

Iterative Transformation Loop

while (seen.count(n) == 0)
{
    if (n == 1)
        return true;

    seen.insert(n);

    int square = 0;
    while (n > 0)
    {
        int digit = n % 10;
        n /= 10;
        square += digit * digit;
    }
    n = square;
}
return false;

The outer while loop continues as long as the current value of n has not been recorded in seen. Inside the loop, the algorithm first checks whether n has reached the happy termination condition (n == 1). If so, it returns true. Otherwise, the current value is inserted into seen to mark it as visited.

The inner while loop extracts each decimal digit of n, squares it, and accumulates the result in square. After processing all digits, n is updated to the newly computed square, and the outer loop repeats with this transformed value.

When the outer loop encounters a value already present in seen, the cycle detection triggers and the function returns false, indicating that n is not a happy number.

Edge Cases Handled

The algorithm gracefully handles the situation where the input n is already 1. The very first iteration of the outer loop evaluates if (n == 1) before any insertion into seen, causing an immediate return of true. This avoids unnecessary work for the trivial happy case.

Another implicit edge case is the handling of n equal to 0. The inner digit-extraction loop (while (n > 0)) will not execute, leaving square at 0. The outer loop then sees that 0 has not been seen before, inserts it, and repeats the process. Since 0 maps to 0 indefinitely, the set eventually contains 0 and the loop terminates, returning false. Thus, the code correctly identifies 0 as not happy without entering an infinite loop.

The use of an unordered_set ensures that any repeated value, regardless of how large the cycle may be, is detected promptly. This covers cycles of varying lengths, including the well-known unhappy cycle 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4.

Performance Optimizations

The implementation leverages several implicit optimizations:

• Constant-time cycle detection: By storing previously seen values in an unordered_set, the algorithm achieves O(1) average-case checks for repetition, avoiding the need for slower linear scans.

• In-place digit processing: The inner loop modifies n directly while extracting digits, eliminating the need for auxiliary containers or string conversions. This reduces memory overhead and improves cache locality.

• Early termination on happy condition: The check if (n == 1) is placed at the start of each outer iteration, allowing the function to exit immediately once the happy state is reached, without performing further insertions or digit calculations.

• Minimal temporary storage: Only a single integer square is used to accumulate the digit-square sum, keeping the stack footprint small and avoiding unnecessary heap allocations.

Collectively, these choices result in a solution that runs efficiently for typical integer ranges, quickly converging to a result while using modest memory.

Imagine a toy box that keeps track of every number it has seen before. The code starts with a special number and puts it into the toy box. Then, it takes that number apart, squares each piece, and adds those squares together to make a new number.

The computer checks to see if this new number is already in the toy box. If the number is a one, it means success and the puzzle is finished. If the number is not in the toy box, the computer adds it there and keeps repeating the same trick of squaring the pieces to make another new number.

If the computer ever sees a number that is already sitting inside the toy box, it knows it is stuck in a loop and will never reach the number one. This process follows a clear set of rules to see how numbers change until they either turn into one or start repeating themselves forever.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: logarithmic
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		C	Rust		Go			TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei						Rust
	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	everthis							JS
	fartem									Ruby
	FelixFan1122				C#
	gaosq0604		Python
	halfrost								Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	lzl124631x	C++
	muhammadfarhankt								Go
	qiyuangong		Python
	ruoru						Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28			Java
	vli02					C
	vthwang			Java
	yuanliu666										Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
gaosq0604	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
lzl124631x	C++
muhammadfarhankt	Go
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality