# Square Root of Integer

Problem Statement: Given an integer `A`. Compute and return the `square root of A`. If `A` is not a perfect square, return `floor(sqrt(A))`. The value of `A` can cross the range of Integer.

#### Examples:

Example 1:

Input: 11

Output: 3

Explanation 1: When A = 11, the square root of A = 3.316. It is not a perfect square so we return the floor which is 3.

Example 2:

Input: 9

Output: 3

Explanation 2: When A = 9 which is a perfect square of 3, so we return 3.

Problem Constraints: `0 <= A <= 1010`

#### Solutions:

Disclaimer: Donâ€™t directly jump into the solution, first try it yourself.

Approach 1: Brute Force Approach

This approach is simple just iterate `i` from 1 to A and calculate `(i*i)` until we get `i*i = A or ((i+1)*(i+1)) > A`. Once we reach this condition just return `i` the value as output. The value `i` will be the `Sqrt(A)`.

Code:

```class Coderzpy {

int sqrt(int A) {

long ans = 0;

for(long i = 0; i <= A; i++){

if(i*i == A || (i+1)*(i+1) > A {
ans = i;
}

}

return (int) ans;
}

public static void main(String args[]) {

int A = 11;

System.out.println("The sqrt is: "+
sqrt(A));
}
}
```

output: The sqrt is: 3

Time Complexity: O(sqrt(n)) for iterating each element until it reaches the `i*i = sqrt(A)`;

Space Complexity: O(1).

Approach 2: Optimized Approach

In this approach, we are going to use Binary Search, to optimize the search time complexity by searching the elements within a confined search space.

Code:

```class Coderzpy {

public int sqrt(int A) {

long left = 0;
long right = A;

while(left <= right) {

long mid = (left + right) / 2;

if(A == 2 || A == 1) {

return 1;
}

if(mid*mid == A || (mid*mid < A &amp;&amp; (mid+1)*(mid+1) > A)) {

return (int)mid;
}

if(mid*mid < A) {

left = mid+1;

}else {

right = mid-1;
}
}

return 0;
}

public static void main(String args[]) {

int A = 11;

System.out.println("The sqrt is: "+
sqrt(A));
}
}
```

output: The sqrt is: 3

Time Complexity: O(log(n)) because using Binary Search to find the `sqrt(A)`;

Space Complexity: O(1).