Problem List

Sqrt(x)

May 31, 2025 • Go • math, binary search • easy

Problem

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.

Reflections

The binary search topic tag kind of gave it away.

Performance

Runtime beats: 100%
Memory beats: 85%

Complexity

Time: O(log n)
Space: O(log n)

Go Solution

func mySqrt(x int) int {
  left, right := 1, x

  for left <= right {
    mid:= left + ((right - left) / 2)

        mid2:= mid * mid

        if mid2 < x {
      left = mid + 1
    } else if mid2 > x {
      right = mid - 1
    } else {
    return mid
  }
}

return right
}

LeetCode Problem Link