Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/69.html

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.

 

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

 

Constraints:

  • 0 <= x <= 231 - 1

Algorithm

Binary search method to find square root.

Code

  • 
public class Sqrt_x {

    public class Solution {

        // @memorize: divide and conquer, in fact it's a binary search. compare with pow() question
        public int mySqrt(int x) {
            // @note: x < 0, then return Imaginary number?
            // proof: sqrt(x) <= x/2, then, x <= x^2/4, then, x^2 - 4x >= 0, then x>=4

            if (x < 0) {
                return -1;
            }

            if (x == 0 || x == 1) {
                return x;
            }

            int low = 1; // lowBoundary
            int up = x; // upBoundary
            int mid = -1;
            while (low <= up) {
                mid = low + (up - low) / 2;

                // if (mid * mid == x) // @note: overflow
                if (mid <= x / mid && (mid + 1) > x / (mid + 1)) { // eg: 2^2 <=5, 3^2 > 5
                    return mid;
                } else if (mid < x / mid) {
                    low = mid + 1;
                } else {
                    up = mid - 1;
                }
            }

            return mid;
        }
    }

}


############

class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x;
        while (left < right) {
            int mid = (left + right + 1) >>> 1;
            if (mid <= x / mid) {
                // mid*mid <= x
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

  • // OJ: https://leetcode.com/problems/sqrtx/
// Time: O(sqrt(N))
// Space: O(1)
class Solution {
public:
    int mySqrt(int x) {
        long i = 0;
        while (i * i <= x) ++i;
        return i - 1;
    }
};

  • class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        while left < right:
            mid = (left + right + 1) >> 1
            # mid*mid <= x
            if mid <= x // mid:
                left = mid
            else:
                right = mid - 1
        return left

############

class Solution(object):
  def mySqrt(self, x):
    """
    :type x: int
    :rtype: int
    """
    lo = 0
    hi = x
    while lo <= hi:
      mid = (hi + lo) // 2
      v = mid * mid
      if v < x:
        lo = mid + 1
      elif v > x:
        hi = mid - 1
      else:
        return mid
    return hi


  • func mySqrt(x int) int {
	left, right := 0, x
	for left < right {
		mid := left + (right-left+1)>>1
		if mid <= x/mid {
			left = mid
		} else {
			right = mid - 1
		}
	}
	return left
}

  • /**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
    let left = 0;
    let right = x;
    while (left < right) {
        const mid = (left + right + 1) >>> 1;
        if (mid <= x / mid) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
};


  • public class Solution {
    public int MySqrt(int x) {
        int left = 0, right = x;
        while (left < right)
        {
            int mid = left + right + 1 >> 1;
            if (mid <= x / mid)
            {
                left = mid;
            }
            else
            {
                right = mid - 1;
            }
        }
        return left;
    }
}

  • impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x < 2 {
            return x;
        }
        let mut l = 1;
        let mut r = x / 2;
        while l < r {
            let mid = (l + r + 1) >> 1;
            if x / mid < mid {
                r = mid - 1
            } else {
                l = mid;
            }
        }
        l
    }
}

All Problems

All Solutions