Sqrtx

Math Binary Search

41.4% acceptance

Jan 12, 2026

9607

4636

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn my_sqrt(x: i32) -> i32 {
    if x == 0 {
      return 0;
    }
    
    // Newton's method: faster convergence than binary search
    let mut r = x as i64;
    while r * r > x as i64 {
      r = (r + x as i64 / r) / 2;
    }
    
    r as i32
  }
}