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).