LeetCode #69: Sqrt(x) (C/C++).

easy

source: https://leetcode.com/problems/sqrtx/
C/C++ Solution to LeetCode problem 69. Sqrt(x).

Problem

---

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.

Examples

---

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

Solution

---

This can be solved with Binary Search where the mid value is the candidate sqrt.

class Solution {
public:
  int mySqrt(int x) {
    int l=0;
    int r=x;
    int res = 0;

    while (l<=r) {
      long int m = (l+r) / 2;

      if ((m*m) == x)
        return m;
      else if ((m*m) > x)
        r = m - 1;
      else {
        l = m + 1;
        res = m;
      }
    }
    return res;
  }
};