Sqrt(x)
Post
Cancel

# 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 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; } };