69. Sqrt(x) - Solution & Explanation

The problem

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 <= 2³¹ - 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.

Python

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        left, right = 1, x // 2
        while left <= right:
            mid = (left + right) // 2
            if mid <= x // mid:
                left = mid + 1
            else:
                right = mid - 1
        return right

sol = Solution()
x = 8
print(sol.mySqrt(x))  # Output: 2

Java

public class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        int left = 1, right = x / 2;
        int ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int x = 8;
        System.out.println(sol.mySqrt(x));  // Output: 2
    }
}

C++

#include <iostream>
using namespace std;

class Solution {
public:
    int mySqrt(int x) {
        if (x < 2) return x;
        int left = 1, right = x / 2, mid, sqrt;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (mid <= x / mid) {
                left = mid + 1;
                sqrt = mid;
            } else {
                right = mid - 1;
            }
        }
        return sqrt;
    }
};

int main() {
    Solution sol;
    int x = 8;
    cout << sol.mySqrt(x) << endl;  // Output: 2
    return 0;
}

JavaScript

function mySqrt(x) {
    if (x < 2) return x;
    let left = 1, right = Math.floor(x / 2);
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (mid <= Math.floor(x / mid)) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
}

let x = 8;
console.log(mySqrt(x));  // Output: 2

#include <stdio.h>

int mySqrt(int x) {
    if (x < 2) return x;
    int left = 1, right = x / 2, mid;
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (mid <= x / mid) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
}

int main() {
    int x = 8;
    printf("%d", mySqrt(x));  // Output: 2
    return 0;
}

public class Solution {
    public int MySqrt(int x) {
        if (x < 2) return x;
        int left = 1, right = x / 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int x = 8;
        Console.WriteLine(sol.MySqrt(x));  // Output: 2
    }
}

This Python solution uses binary search to find the integer square root. It divides the problem space into half iteratively until the square root is found within the defined precision.

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.

Python

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        g = x
        while g * g > x:
            g = (g + x // g) // 2
        return int(g)

sol = Solution()
x = 8
print(sol.mySqrt(x))  # Output: 2

Java

public class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        double g = x;
        while (g * g > x) {
            g = (g + x / g) / 2;
        }
        return (int)g;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int x = 8;
        System.out.println(sol.mySqrt(x));  // Output: 2
    }
}

C++

#include <iostream>
using namespace std;

class Solution {
public:
    int mySqrt(int x) {
        if (x < 2) return x;
        double g = x;
        while (g * g > x) {
            g = (g + x / g) / 2;
        }
        return (int)g;
    }
};

int main() {
    Solution sol;
    int x = 8;
    cout << sol.mySqrt(x) << endl;  // Output: 2
    return 0;
}

JavaScript

function mySqrt(x) {
    if (x < 2) return x;
    let g = x;
    while (g * g > x) {
        g = Math.floor((g + x / g) / 2);
    }
    return g;
}

let x = 8;
console.log(mySqrt(x));  // Output: 2

#include <stdio.h>

int mySqrt(int x) {
    if (x < 2) return x;
    double g = x;
    while (g * g > x) {
        g = (g + x / g) / 2.0;
    }
    return (int)g;
}

int main() {
    int x = 8;
    printf("%d", mySqrt(x));  // Output: 2
    return 0;
}

public class Solution {
    public int MySqrt(int x) {
        if (x < 2) return x;
        double g = x;
        while (g * g > x) {
            g = (g + x / g) / 2;
        }
        return (int)g;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int x = 8;
        Console.WriteLine(sol.MySqrt(x));  // Output: 2
    }
}

The Python solution employs Newton's method to iteratively approach the integer square root by refining the guess until convergence.

Complexity

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

Try this approach in the editor

Approach 3: Binary Search

We define the left boundary of the binary search as l = 0 and the right boundary as r = x, then we search for the square root within the range [l, r].

In each step of the search, we find the middle value mid = (l + r + 1) / 2. If mid > x / mid, it means the square root is within the range [l, mid - 1], so we set r = mid - 1. Otherwise, it means the square root is within the range [mid, r], so we set l = mid.

After the search ends, we return l.

The time complexity is O(log x), and the space complexity is O(1).

func mySqrt(x int) int {
	return sort.Search(x+1, func(i int) bool { return i*i > x }) - 1
}

Rust

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        let mut l = 0;
        let mut r = x;

        while l < r {
            let mid = (l + r + 1) / 2;

            if mid > x / mid {
                r = mid - 1;
            } else {
                l = mid;
            }
        }

        l
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Binary Search	Time Complexity: O(log x) Space Complexity: O(1)
Newton's Method	Time Complexity: O(log x) Space Complexity: O(1)
Binary Search	–

Complexity analysis

Approach	Time	Space	When to Use
Linear Iteration	O(sqrt(n))	O(1)	Good for conceptual understanding or very small inputs
Binary Search	O(log n)	O(1)	Standard interview solution using monotonic search space
Newton's Method	O(log n)	O(1)	When fast numerical convergence or mathematical optimization is preferred

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.

Sqrt(x) solution and explanation

The problem

Approach overview

Approach 1: Binary Search

Approach 2: Newton's Method

Approach 3: Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Sqrt(x) solution and explanation

The problem

Approach overview

Approach 1: Binary Search

Approach 2: Newton's Method

Approach 3: Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems