69. Sqrt(x) (Leetcode || Java || Easy)

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 <= 231 - 1

SOLUTION:

1. Brute force solution

class Solution {
public int mySqrt(int x) {
if(x < 2){//if x is less than 2, say, 0 or 1, then there square root is the number itself and as given in the constraints x can’t be less than 0
return x;
}

int i = 1;
while((long)i*i <= x){//As i*i can be greater than what the int value can hold, so it is necessary to use long data type
i++;
}
return i — 1;
}
}

TIME COMPLEXITY :- O(N/2)

SPACE COMPLEXITY :- O(1)

2)BINARY SEARCH METHOD

class Solution {
public int mySqrt(int x) {
if(x < 2){//Since the square root of 0 and 1 is the number itself
return x;
}

int start = 1;
int end = x/2;//The square root of any number can’t exceed its half

while(start <= end){//Applying binary search here, since we are searching in a range
int mid = start + (end — start)/2;

if((long) mid*mid > x){
end = mid — 1;
}else{
start = mid + 1;
}
}

return end;
}
}

TIME COMPLEXITY :- O(log(n))

SPACE COMLEXITY :- O(1)

Thank you for reading. If you have any queries, then please let me know in the comment section.