‹ DS&A interview · Socratic
DSA · Binary Search · #169

Sqrt(x)

Module 59 · difficulty 2/5·⏱ 30:00starts on first keystroke

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 (e.g. `Math.pow(x, 0.5)` or `Math.sqrt(x)`). Implement the function `mySqrt(x)`.

Examples
  • x = 4 → 2 — The square root of 4 is 2, so we return 2.
  • x = 8 → 2 — The square root of 8 is 2.828..., so we return 2 (rounded down).
  • x = 0 → 0
Constraints
  • · 0 <= x <= 2^31 - 1
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.