Skip to main content
Talentd

Sqrt(x) - Solution & Explanation

EasyMathBinary Search13 min readAsked at: Amazon, Microsoft, Apple +14
Practice this problem

Problem Statement

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

  • For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

 

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

 

Constraints:

  • 0 <= x <= 231 - 1

Approach Overview

Problem Overview: Given a non‑negative integer x, compute and return the integer square root of x. The result must be truncated to the nearest integer (floor value). You cannot use built‑in exponent or square root functions.

Approach 1: Linear Iteration (O(sqrt(n)) time, O(1) space)

The simplest idea is to try every integer starting from 1 and stop when i * i becomes greater than x. The last valid i where i * i ≤ x is the answer. This approach directly models the mathematical definition of square root. However, it performs up to sqrt(x) iterations, which becomes slow for large inputs such as x = 2^31 - 1. This version is useful for understanding the problem before moving to logarithmic solutions.

Approach 2: Binary Search (O(log n) time, O(1) space)

The square root function is monotonic: as i increases, i * i also increases. That means you can search the answer using binary search. Define a search range from 1 to x. Compute mid, then compare mid * mid with x. If it's equal, return mid. If it's smaller, move the left boundary to search for a larger value. If it's larger, shrink the right boundary. The final answer is the largest mid where mid * mid ≤ x. This reduces the search space by half each step, giving O(log x) time. The approach relies purely on arithmetic and is a common application of math reasoning combined with binary search.

Approach 3: Newton's Method (O(log n) time, O(1) space)

Newton's Method (also called Newton–Raphson) uses numerical optimization to approximate square roots. Start with an initial guess r = x. Repeatedly update the estimate using r = (r + x / r) / 2. Each iteration moves the estimate closer to the true square root. Stop when r * r ≤ x. This method converges extremely fast, usually within a few iterations even for large numbers. It’s widely used in numerical computing and demonstrates deeper mathematical insight compared to brute approaches.

Recommended for interviews: Binary Search is the most expected solution. It shows you recognize the monotonic property and can apply logarithmic search correctly. The linear scan demonstrates basic reasoning but lacks efficiency. Newton's Method is impressive if you know it, though many interviewers are perfectly satisfied with the binary search solution.

Approach 1: Binary Search

This approach uses binary search to find the integer square root of the given number x. The idea is to use a binary search over the range [0, x] to find the largest number whose square is less than or equal to x. The time complexity of this approach is logarithmic, which makes it very efficient.

This implementation uses binary search. The mySqrt function initializes two pointers, left and right, to define the search space. The mid-point is calculated, and the square of the mid-point is compared with x. The search space is adjusted accordingly until it converges.

Code

CC++JavaPythonC#JavaScriptGoRust

C

C++

Java

Python

C#

JavaScript

Go

Rust

Complexity

Time Complexity: O(log x)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Newton's Method

Newton's Method (also known as the Newton-Raphson method) can also be applied to find the square root of a number through iteration. The general formula for updating a guess g is g = (g + x/g) / 2. This keeps refining the guess based on how close it is to x/g.

This implementation uses Newton's method to find the square root. It initializes g as the guess, and iteratively updates g until g * g is sufficiently close to x.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log x)
Space Complexity: O(1)

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search

Time Complexity: O(log x)
Space Complexity: O(1)

Newton's Method

Time Complexity: O(log x)
Space Complexity: O(1)

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear IterationO(sqrt(n))O(1)Good for conceptual understanding or very small inputs
Binary SearchO(log n)O(1)Standard interview solution using monotonic search space
Newton's MethodO(log n)O(1)When fast numerical convergence or mathematical optimization is preferred

Video Solution

Sqrt(x) - Leetcode 69 - Python • NeetCodeIO • 132,652 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sqrt(x) easy or hard?
Sqrt(x) is classified as an Easy problem on LeetCode but still tests key interview skills. Candidates must recognize the monotonic property and apply binary search correctly while handling edge cases and integer overflow.
Sqrt(x) Python/Java solution
Python and Java implementations typically use binary search with two pointers (left and right). Each iteration computes mid and compares mid * mid with x while preventing overflow. The same logic works in C++, JavaScript, and other languages.
How to solve Sqrt(x) in O(log n)?
Use Binary Search on the range [1, x]. Compute mid, then compare mid * mid with x. If mid * mid ≤ x, move the left pointer to mid + 1 and store mid as a candidate answer; otherwise move the right pointer left. This guarantees O(log x) time complexity.
What is the best approach for Sqrt(x)?
Binary Search is the most common and interview‑friendly solution. The search space ranges from 1 to x, and each step checks whether mid * mid is greater or smaller than x. Because the search space halves each iteration, the algorithm runs in O(log x) time with O(1) space.
Is Sqrt(x) asked at Google/Amazon/Meta?
Sqrt(x) is a common interview problem because it tests binary search reasoning and integer overflow awareness. Variants of this question have appeared in interviews at companies like Google, Amazon, and Meta when evaluating algorithm fundamentals.
What data structure is used in Sqrt(x)?
The problem mainly relies on mathematical reasoning and binary search rather than complex data structures. The algorithm only uses integer variables to track the search range and compute mid values.
What is the time complexity of Sqrt(x)?
The optimal solutions run in O(log x) time. Binary Search reduces the search range by half each step, while Newton's Method converges rapidly using iterative approximation. Both approaches use constant extra space.

Ready to solve this problem?

Practice Sqrt(x) with our built-in code editor and test cases.

Practice on FleetCode
Previous

Pow(x, n)

Next

Valid Perfect Square