Question

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

Implement int sqrt(int x).

Compute and return the square root of x.

Algorithm

Binary search method to find square root.

Code

Java

  • 
    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;
            }
        }
    
    }
    
    
  • // 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(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
    
    

All Problems

All Solutions