69. Sqrt(x)

🟩 Easy

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

Hint-1

Try exploring all integers. (Credits: @annujoshi)

Hint-2

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

Solution

My Solution

func mySqrt(x int) int {

    mid, left, right := 0, 0, x+1    
    for left < right {
        mid = left + (right-left)/2
        if mid * mid > x {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left - 1
}

Optimal Solution (Binary Search)

func mySqrt(x int) int {
    if x < 2 {
        return x
    }
    
    left, right := 1, x/2
    
    for left <= right {
        mid := left + (right-left)/2
        square := mid * mid
        
        switch {
        case square == x:
            return mid
        case square < x:
            left = mid + 1
        default:
            right = mid - 1
        }
    }
    
    return right
}

Approach

This solution uses binary search to efficiently find the square root:

1. Initial Range:

   • For x ≥ 2, square root is in range [1, x/2]

   • For x < 2, return x directly

   • Using x/2 as upper bound since √x ≤ x/2 for x ≥ 4

2. Binary Search Implementation:

   • Calculate mid point and its square

   • If square equals x, found exact square root

   • If square less than x, search right half

   • If square greater than x, search left half

3. Key Insights:

   • Integer overflow avoided using (right-left)/2

   • Result is floor of actual square root

   • Right pointer ends at floor value

Complexity Analysis

Time Complexity: O(log n)

• Binary search over range [1, x/2]

• Search space halved in each iteration

• Takes log₂(x) steps to converge

Space Complexity: O(1)

• Only uses constant extra space:

  • Three integers (left, right, mid)

  • One temporary for square calculation

Why it works

• Binary Search Properties:

  • Search space is sorted (1 to x/2)

  • Can compare mid² with target

  • Always converges to floor value

• Handling Edge Cases:

  • x < 2 handled separately

  • Overflow prevented in mid calculation

  • Right pointer gives floor value when no exact square

• Correctness:

  • If exact square root exists, found directly

  • If not, right pointer gives floor value

  • All values in [1, x/2] considered

result

Leetcode: link