Sqrt(x)

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.

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
}

Performance

• Runtime beats: 100%
• Memory beats: 85%

Complexity

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