Problem of the day
You are given a positive integer ‘n’.
Your task is to find and return its square root. If ‘n’ is not a perfect square, then return the floor value of sqrt(n).
Input: ‘n’ = 7
Output: 2
Explanation:
The square root of the number 7 lies between 2 and 3, so the floor value is 2.
The first line of input contains the Integer ‘n’.
The output contains an integer denoting the square root of ‘n’.
You do not need to print anything. It has already been taken care of. Just implement the given function.
6
2
The square root of the given number 6 lies between 2 and 3, so the floor value is 2.
100
10
The square root of the given number 100 is 10.
Try solving this in O(log(n)).
0 <= n <= 10 ^ 9
Time Limit: 1 sec.
Continue incrementing the number until the square of that number is greater than the given number.
The idea is to iterate through all numbers and check.
Algorithm :
O(sqrt(N)) where ‘N’ is the given integer.
We are iterating from 1 to sqrt(N) the given number once. So the time complexity is O( sqrt(‘N’) ).
O(1)
We are not using any extra space.