Leetcode 69: Sqrt(x)

1. Problem Statement (Simple Explanation)

You’re given a non-negative integer x.

You must return:

• ⌊√x⌋ — the square root of x rounded down to the nearest integer.

• The result must be non-negative.

• You must not use built-in exponent or sqrt functions (pow, sqrt, x**0.5, etc.).

2. Examples

Example 1:

Input: x = 4

√4 = 2 exactly.

Output: 2

Example 2:

Input: x = 8

√8 ≈ 2.828..., floor is 2.

Output: 2

3. Approach – Binary Search on Answer (O(log x))

We want to find the largest integer m such that: m * m <= x

Because x is up to 231 - 1, m will be at most 46340 (since 463402 < 231 -1, but 463412 overflows 32-bit int).

But we can be general. We can binary search on m in range [0, x]:

• Let left = 0, right = x.

• While left <= right:

• mid = left + (right - left) / 2.

• Compute mid * mid (use 64-bit / long to avoid overflow).

• If mid2 == x, return mid.

• If mid2 < x, move left = mid + 1 (try a larger mid).

• Else (mid2 > x), move right = mid - 1.

When loop ends:

• right will hold the largest m with m2 <= x.

• Return right.

Pseudo-code:

Note: instead of checking mid * mid <= x, we use mid <= x / mid (safe with 32-bit int).

Complexity:

• Time: O(logx)

• Space: O(1)

4. Java code

5. C code

6. C++ code

7. Python code

8. JavaScript code

9. Alternative Approach – Newton’s Method (Optional)

Newton’s iterative method for y = sqrt(x):

• Start with a guess r = x.

• Iterate: r = (r + x / r) / 2

until r^2 is close to x. Then return int(r).

Time complexity is also O(log x) in practice, but binary search is simpler and robust.