69. Sqrt(x)

Description

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

Examples

Example 1

Input: 8

Output: 2

Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Example 2

Input: 4

Output: 2

Solutions

Solution 1

/**
 * 
 * 
 */

class Solution {
    public int mySqrt(int x) {
        if(x == Integer.MAX_VALUE) x--;
        int p = x, q = 1;
        while(p-q > 0.1) {
            p = (p + q)/2;
            q = x/p;
        }
        return (int)p;
    }
}

Follow up