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 && (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).
Follow Me
If you like my post please follow me to read my latest post on programming and technology.
https://www.instagram.com/coderz.py/
https://www.facebook.com/coderz.py
