[LeetCode 69] Sqrt(x)

문제 바로가기

Description

---

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 <= 2^31 - 1

Hint

---

Hint 1

  Try exploring all integers. (Credits: @annujoshi)
	

Hint 2

  Use the sorted property of integers to reduced the search space. (Credits: @annujoshi)
	

Code

---

내 제출

---

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x;
        while (l < r) {
            int mid = (l + r + 1) >>> 1;
            if (mid > x / mid) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        //System.out.println(x);
        return l;
    }
}

Runtime	Memory
1 ms	40.8 MB

다른 풀이

---

class Solution {
    public int mySqrt(int x) {
      if(x==0||x==1)
      return x;
      int start=1;
      int end=x;
      int mid=-1;
      while(start<=end){
        mid=start+(end-start)/2;
        if((long)mid*mid>(long)x)
        end=mid-1;
        else if(mid*mid==x)
        return mid;
        else
        start=mid+1;
      } 
      return Math.round(end);
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/0000-0099/0069.Sqrt(x)/Solution.java