69.sqrtx.js

/*
  ✔ Accepted
  ✔ 1017/1017 cases passed (72 ms)
  ✔ Your runtime beats 47.97 % of javascript submissions
*/
/*
 * [69] Sqrt(x)
 *
 * https://leetcode.com/problems/sqrtx/description/
 *
 * algorithms
 * Easy (29.55%)
 * Total Accepted:    275.4K
 * Total Submissions: 932K
 * Testcase Example:  '4'
 *
 * Implement int sqrt(int x).
 * 
 * Compute and return the square root of x, where x is guaranteed to be a
 * non-negative integer.
 * 
 * Since the return type is an integer, the decimal digits are truncated and
 * only the integer part of the result is returned.
 * 
 * Example 1:
 * 
 * 
 * Input: 4
 * Output: 2
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: 8
 * Output: 2
 * Explanation: The square root of 8 is 2.82842..., and since 
 * the decimal part is truncated, 2 is returned.
 * 
 * 
 */
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
  if (x === 0) return 0;
  let ans = x;
  while (ans*ans > x) {
    ans = Math.floor((ans + x / ans) / 2);
  }
  return ans;
};