This solution is generated by ChatGPT, correctness is not guaranteed. You might also be able to find a solution fromcommunity posts.

AI solution for JavaScript Coding Question on BFE.dev
103. implement Math.sqrt()

One possible solution for mySqrt() is to use binary search to find the integer square root.

function mySqrt(x) {  // Special case  if (x === 0) return 0;  // Binary search for integer square root  let left = 1, right = x;  while (left <= right) {    let mid = Math.floor((left + right) / 2);    if (mid * mid === x) return mid;    if (mid * mid < x) {      left = mid + 1;    } else {      right = mid - 1;    }  }  // Return the floor of the last mid  return right;}

The time complexity of this solution is O(log x) and the space complexity is O(1), as we only use a few constant variables.

This solution is already optimal in terms of time complexity, but there is a way to improve the space complexity. Instead of using the left and right variables to track the range of possible square roots, we can simply define two pointers and update them until they meet:

function mySqrt(x) {  // Special case  if (x === 0) return 0;  // Binary search for integer square root with two pointers  let lo = 1, hi = x;  while (lo < hi) {    let mid = Math.floor((lo + hi) / 2);    if (mid * mid === x) return mid;    if (mid * mid < x) {      lo = mid + 1;    } else {      hi = mid - 1;    }  }  // Return the floor of the last mid  return lo * lo > x ? lo - 1 : lo;}

This solution still has a time complexity of O(log x), but the space complexity is now O(1).