Sqrt(x)

LeetCode 69 | Difficulty: Easy

Easy

Problem Description

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^31 - 1`

Topics: Math, Binary Search

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 65 ms)

Metric	Value
Runtime	65 ms
Memory	N/A
Date	2017-10-22

Solution

public class Solution {
    public int MySqrt(int x) {
    if(x==0) return 0;
    var approx = 0.5 * x;
    double betterapprox = 0.0;
    while(true)
    {
        betterapprox = 0.5 * (approx + x / approx);
        if (approx - betterapprox < 0.001)
        {
            break;
        }
        approx = betterapprox;      
    }
    return (int)betterapprox;
}
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Precisely define what the left and right boundaries represent, and the loop invariant.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Try exploring all integers. (Credits: @annujoshi)

Hint 2: Use the sorted property of integers to reduced the search space. (Credits: @annujoshi)