Skip to main content
CodePeetCodePeet
CodePeet 250

Sqrt(x)

EASYProblemSolveExternal Links

Description

Given a non-negative integer x, compute and return the square root of x, rounded down to the nearest integer (i.e., the floor value).

The returned integer should also be non-negative.

Important restriction: 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.

Examples

Example 1

Input: x = 4

Output: 2

Explanation: The square root of 4 is exactly 2.0, so we return 2. Since 2 × 2 = 4, and 4 equals x, the answer is a perfect square root.

Example 2

Input: x = 8

Output: 2

Explanation: The actual square root of 8 is approximately 2.82842. Since we must round down to the nearest integer, we return 2. Notice that 2 × 2 = 4 ≤ 8, but 3 × 3 = 9 > 8, confirming that 2 is the largest integer whose square does not exceed 8.

Example 3

Input: x = 0

Output: 0

Explanation: The square root of 0 is 0. This is an edge case where the input is zero.

Example 4

Input: x = 1

Output: 1

Explanation: The square root of 1 is exactly 1. Since 1 × 1 = 1, the answer is 1.

Constraints

  • 0 ≤ x ≤ 2^31 - 1

Editorial

Brute Force

Intuition

The most straightforward way to find the integer square root is to simply try every integer starting from 1 and check if its square exceeds x.

Imagine you are building a square garden and you have x tiles. You start with a 1×1 garden (1 tile), then try 2×2 (4 tiles), then 3×3 (9 tiles), and so on. The moment the garden requires more tiles than you have, you know the previous size was the largest square garden you could build.

Specifically, we iterate i from 1 upward. As long as i * i ≤ x, i is a valid candidate for the answer. The moment i * i > x, we stop and return i - 1, since that is the largest integer whose square fits within x.

Step-by-Step Explanation

Let's trace through with x = 8:

Step 1: Start with i = 1. Compute i² = 1 × 1 = 1. Is 1 ≤ 8? Yes. So i = 1 is a valid candidate. Record result = 1.

Step 2: Move to i = 2. Compute i² = 2 × 2 = 4. Is 4 ≤ 8? Yes. So i = 2 is a valid candidate. Update result = 2.

Step 3: Move to i = 3. Compute i² = 3 × 3 = 9. Is 9 ≤ 8? No! 9 exceeds 8.

Step 4: Since i² > x, we stop the loop. The last valid candidate was i = 2.

Step 5: Return result = 2. This means 2 is the largest integer whose square does not exceed 8.

Brute Force — Linear Scan for Floor Square Root — Watch how we try each integer starting from 1, squaring it, and checking whether the square exceeds x. The last valid candidate becomes our answer.

Algorithm

  1. Handle edge case: if x is 0, return 0
  2. Initialize a variable result = 0
  3. Iterate i from 1 upward:
    • If i * i ≤ x, update result = i
    • If i * i > x, break out of the loop
  4. Return result

Note: To avoid integer overflow when computing i * i for large values, cast i to a long before multiplication.

Code

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        int result = 0;
        for (long i = 1; i * i <= x; i++) {
            result = (int)i;
        }
        return result;
    }
};
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        result = 0
        i = 1
        while i * i <= x:
            result = i
            i += 1
        return result
class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int result = 0;
        for (long i = 1; i * i <= x; i++) {
            result = (int) i;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(√x)

We iterate from 1 up to √x. The loop terminates once i * i exceeds x, which happens when i reaches approximately √x. For x = 2^31 - 1 ≈ 2.1 × 10^9, that means iterating up to about 46,340 times.

Space Complexity: O(1)

We use only a few integer variables (i, result) regardless of the input size. No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force approach iterates through every integer from 1 to √x, performing O(√x) iterations. While this is acceptable for the given constraints (√(2^31) ≈ 46,340 iterations), we are performing a linear search through a space that is inherently sorted and monotonic — as i increases, i² also increases.

Whenever we have a sorted search space with a clear condition that divides the space into two halves (values whose square is ≤ x on the left, values whose square is > x on the right), we can use binary search to find the boundary in O(log x) time instead of O(√x) time.

For x = 2^31 - 1, binary search would need only about 31 iterations compared to 46,340 for the linear scan — a speedup of over 1,000×.

Optimal Approach - Binary Search

Intuition

The key insight is that the squares of integers form a sorted sequence: 1, 4, 9, 16, 25, 36, ... This means if we know that mid² is too large (greater than x), then every integer above mid is also too large. Conversely, if mid² is small enough (≤ x), then every integer below mid is also small enough.

This is exactly the pattern binary search exploits. We set up a search range from 1 to x, pick the middle value, and compare its square to x:

  • If mid² ≤ x: mid is a potential answer. The true answer might be even larger, so we search the right half (and remember mid as a candidate).
  • If mid² > x: mid is too large. The answer must be smaller, so we search the left half.

Think of it like guessing someone's height. If you guess 170 cm and they say "taller," you eliminate everything below 170. If you guess 180 cm and they say "shorter," you eliminate everything above 180. Each guess halves the remaining possibilities.

By repeatedly halving the search range, we find the answer in O(log x) steps instead of O(√x).

Step-by-Step Explanation

Let's trace through with x = 8:

Step 1: Initialize the search range: lo = 1, hi = 8, result = 0.

Step 2: Compute mid = 1 + (8 - 1) / 2 = 4. Compute mid² = 4 × 4 = 16.

  • Is 16 ≤ 8? No. 16 > 8, so 4 is too large.
  • Shrink the search range: hi = mid - 1 = 3. Search range becomes [1, 3].

Step 3: Compute mid = 1 + (3 - 1) / 2 = 2. Compute mid² = 2 × 2 = 4.

  • Is 4 ≤ 8? Yes! So 2 is a valid candidate.
  • Update result = 2. The answer might be even larger, so search right: lo = mid + 1 = 3. Search range becomes [3, 3].

Step 4: Compute mid = 3 + (3 - 3) / 2 = 3. Compute mid² = 3 × 3 = 9.

  • Is 9 ≤ 8? No. 9 > 8, so 3 is too large.
  • Shrink: hi = mid - 1 = 2. Now lo (3) > hi (2), so the loop ends.

Step 5: Return result = 2. Binary search confirmed that 2 is the largest integer whose square does not exceed 8, in just 3 iterations.

Binary Search for Integer Square Root — Watch how binary search narrows the candidate range by half at each step, finding the floor square root in O(log x) time.

Algorithm

  1. Handle edge cases: if x is 0 or 1, return x directly
  2. Initialize lo = 1, hi = x, result = 0
  3. While lo ≤ hi:
    • Compute mid = lo + (hi - lo) / 2 (avoids overflow)
    • If mid * mid ≤ x:
      • Update result = mid (mid is a valid candidate)
      • Set lo = mid + 1 (search for a potentially larger answer)
    • Else (mid * mid > x):
      • Set hi = mid - 1 (mid is too large, search smaller)
  4. Return result

Overflow note: Use long for the mid * mid computation. When mid is close to √(2^31), mid * mid can exceed the range of a 32-bit integer.

Code

class Solution {
public:
    int mySqrt(int x) {
        if (x < 2) return x;
        
        int lo = 1, hi = x, result = 0;
        
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            
            if (mid * mid <= x) {
                result = (int)mid;
                lo = (int)mid + 1;
            } else {
                hi = (int)mid - 1;
            }
        }
        
        return result;
    }
};
class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        lo, hi = 1, x
        result = 0
        
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            
            if mid * mid <= x:
                result = mid
                lo = mid + 1
            else:
                hi = mid - 1
        
        return result
class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        
        int lo = 1, hi = x, result = 0;
        
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            
            if (mid * mid <= (long) x) {
                result = (int) mid;
                lo = (int) mid + 1;
            } else {
                hi = (int) mid - 1;
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(log x)

Binary search halves the search range at every iteration. Starting from a range of size x, we need at most ⌈log₂(x)⌉ iterations to converge. For x = 2^31 - 1, this is about 31 iterations — an enormous improvement over the O(√x) ≈ 46,340 iterations of the brute force.

Space Complexity: O(1)

We use only a constant number of variables (lo, hi, mid, result). No additional data structures are needed regardless of input size.