Abstract / Summary

Given a non negative integer return its integer square root without using built in functions.

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 42% (7+ million submissions).

Typical patterns to solve this problem:

• Binary Search
• Math

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 function implements an integer square-root calculation for a non-negative 32-bit integer x. It returns the greatest integer guess such that guess * guess does not exceed x. The algorithm follows a deterministic binary-search-like process that works entirely with integer arithmetic and avoids floating-point operations.

Key Steps

Initialization

int64_t step = 1 << 16;
int guess = 0;

The variable step is seeded with 2^16 (65536). This value is larger than the maximum possible integer square root for a 32-bit signed integer (46340), guaranteeing that the first comparison will always be safe. guess starts at zero and will be incrementally built up to the final result.

Iterative Refinement Loop

while (step > 0)
{
    if ((guess + step) * (guess + step) <= x)
        guess += step;
    step >>= 1;
}

The loop runs while step remains positive. In each iteration the algorithm tests whether adding the current step to guess would keep the square within the bound x. If the test succeeds, step is added to guess. Regardless of the test outcome, step is halved by a right-shift, preparing the next finer granularity. This pattern mirrors a binary search on the possible square-root values, narrowing the search space by powers of two.

Return

return guess;

After the loop finishes, guess holds the integer square root and is returned to the caller.

Edge Cases Handled

When x is zero, the condition (guess + step) * (guess + step) <= x never becomes true because any positive step would produce a positive square. Consequently guess stays at zero and the function returns zero, which is the correct square root.

For x equal to one, the first iteration where step is 65536 fails the test, but as step halves repeatedly, the condition becomes true when step reaches one. At that point guess is incremented to one, and the loop continues with step becoming zero, yielding the correct result.

The algorithm also correctly processes the maximum 32-bit signed integer (INT_MAX). The multiplication (guess + step) * (guess + step) is performed in 64-bit arithmetic because step is a 64-bit value, preventing overflow even when the intermediate square exceeds the 32-bit range. The comparison against x remains valid because x is promoted to 64-bit for the comparison.

Performance Optimizations

The implementation achieves a fixed number of iterations equal to the number of bits in the initial step value (16). Each iteration performs a single multiplication and a comparison, both of which are inexpensive integer operations. By starting with a power-of-two step that exceeds any possible result, the algorithm eliminates the need for dynamic bounds calculation and reduces branching overhead.

Using bitwise shift operators (<< and >>) for scaling step is faster than arithmetic multiplication or division. The entire method runs in deterministic time, independent of the magnitude of x, which is advantageous for real-time or embedded contexts where predictable execution time is required.

Imagine you are trying to guess a secret number that, when multiplied by itself, is as close as possible to a big number like one hundred. To find the answer, you start with a big jump called a step. You check if adding that step to your guess makes the result too big. If the result is still smaller than or equal to the big number, you keep that step and add it to your total. Then, you make the step half as small as it was before. You keep doing this over and over again, taking smaller and smaller steps, until you get exactly to the number you are looking for. It is just like playing a game of hot and cold where you constantly narrow down where the answer is hiding. Once the steps get so tiny that they disappear, you know you have found the biggest possible number that stays under or hits your target.

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

not analyzed yet

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	JS		Go
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei						Rust
	begeekmyfriend				C
	BigEggStudy					C#
	black-shadows	C++
	bujosa		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	DimitrisJim				C
	everthis							JS
	fartem								Ruby
	fengvyi	C++
	gaosq0604		Python
	gouthampradhan			Java
	halfrost									Go
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	pruthvikp		Python
	qiyuangong		Python
	ruoru						Rust
	shreymehul					C#
	sonugiri1043	C++
	suxrobGM					C#
	varunu28			Java
	vli02				C
	vthwang			Java
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fengvyi	C++
gaosq0604	Python
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
pruthvikp	Python
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
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