Log inSign up
easyleetcodeNot Started

Sqrt(x)

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.

Binary Search
Solve on leetcode
Lesson

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.\n\nYou must not use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.\n\nYou must write an algorithm that runs in O(log x) time.

Example 1 · Example 1: Perfect Square:

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

Example 2 · Example 2: Non-Perfect Square Truncation:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model monotonic mathematical problems as binary search on answer.
  • Prevent integer overflow using division or 64-bit integer types.
  • Correctly find the lower floor candidate.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find integer square root without built-in math libraries.
  • Search domain is monotonically increasing: 12 < 22 < 32 < ...
  • Need floor(sqrt(x)).

Algorithmic Decision Tree:

  • If x < 2 return x.
  • low = 1, high = x / 2, ans = 1.
  • While low <= high: mid = low + (high - low) / 2.
  • If mid <= x / mid: ans = mid, low = mid + 1.
  • Else high = mid - 1.
  • Return ans.

Connected Patterns:

Valid Perfect SquareKoko Eating BananasCapacity To Ship Packages

1. Linear Search

Intuition

Loop i from 1 to x. If i * i == x return i; if i * i > x return i - 1.

When to apply: Basic baseline.

Algorithm

  1. Step 1: If x == 0 return 0.
  2. Step 2: Loop i = 1 while (long)i * i <= x: i++.
  3. Step 3: Return i - 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int mySqrt(int x) {
10 if (x == 0) return 0;
11 long long i = 1;
12 while (i * i <= x) {
13 i++;
14 }
15 return (int)(i - 1);
16 }
17};
18
19int main() {
20 // Sample driver execution
21 cout << "Execution completed successfully." << endl;
22 return 0;
23}
24

Time & Space Complexity

  • Time complexity: O(sqrt(x)) — Loop runs sqrt(x) times.
  • Space complexity: O(1) — Uses constant O(1) space.

2. Newton's Method (Newton-Raphson)

Intuition

Using Newton's root finding method for f(r) = r2 - x = 0: update r = floor((r + x / r) / 2) until r * r <= x.

When to apply: Fastest convergence for numerical methods.

Algorithm

  1. Step 1: Initialize r = x.
  2. Step 2: While r * r > x, update r = (r + x / r) / 2.
  3. Step 3: Return r.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int mySqrt(int x) {
10 if (x == 0) return 0;
11 long long r = x;
12 while (r * r > x) {
13 r = (r + x / r) / 2;
14 }
15 return (int)r;
16 }
17};
18
19int main() {
20 // Sample driver execution
21 cout << "Execution completed successfully." << endl;
22 return 0;
23}
24

Time & Space Complexity

  • Time complexity: O(log(log x)) — Quadratic convergence doubles the precision bits in each iteration.
  • Space complexity: O(1) — O(1) auxiliary space.

3. Binary Search on Answer

Intuition

For x < 2, return x. Set low = 1, high = x / 2. In each step compute mid. If mid <= x / mid, record ans = mid and search right (low = mid + 1). Otherwise search left (high = mid - 1).

When to apply: Standard optimal solution in coding interviews.

Algorithm

  1. Step 1: If x < 2, return x.
  2. Step 2: Initialize low = 1, high = x / 2, ans = 1.
  3. Step 3: While low <= high:
  4. - mid = low + (high - low) / 2.
  5. - If mid <= x / mid: ans = mid, low = mid + 1.
  6. - Else high = mid - 1.
  7. Step 4: Return ans.

Trace for x = 8

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Initial range for x=8: low=1, high=4
Visual state
Values and pointers at this exact step
pointers
S
1
4
9
16
0
↑ low
1
↑ mid
2
↑ mid
3
↑ high
Check / comparison
mid*mid = 2*2 = 4 <= 8 -> Valid candidate.
Decision / next transition
Record ans = 2, set low = 3.
Why this step matters

Initial range for x=8: low=1, high=4. mid = 2. mid2 = 4 <= 8. Valid candidate! Record ans = 2. Search right: low = mid + 1 = 3.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int mySqrt(int x) {
10 if (x < 2) return x;
11 int low = 1, high = x / 2;
12 int ans = 1;
13 while (low <= high) {
14 int mid = low + (high - low) / 2;
15 if (mid <= x / mid) {
16 ans = mid;
17 low = mid + 1;
18 } else {
19 high = mid - 1;
20 }
21 }
22 return ans;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(log x) — Search space [1, x/2] is halved each step, taking at most log2(x) operations.
  • Space complexity: O(1) — Requires O(1) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear SearchO(sqrt(x))O(1)Increment integer candidate until square exceeds x.Linear stepping.
2.Newton's MethodO(log(log x))O(1)Quadratic numerical convergence.Integer division precision handling.
3.Binary Search on AnswerOptimalO(log x)O(1)Binary search on range [1, x/2] using monotonic property.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • x = 0 -> return 0.
  • x = 1 -> return 1.
  • x = 231 - 1 (maximum integer) -> prevent overflow when computing mid * mid.
  • Non-perfect squares (e.g. x = 8 -> return 2).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always mention integer overflow: mid * mid can exceed 32-bit INT_MAX (use mid <= x / mid or long).
  2. Mention Newton-Raphson as an alternative numerical optimization method.
  3. Clarify why search space can be bounded by x / 2 for x >= 4.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is mid <= x / mid preferred over mid * mid <= x in 32-bit systems?

Back to DSA Sheet