Square Root of a number

Easy
0/40
Average time to solve is 15m
383 upvotes
Asked in companies
SamsungGoogleAmazon

Problem statement

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).


Example:
Input: ‘n’ = 7

Output: 2

Explanation:
The square root of the number 7 lies between 2 and 3, so the floor value is 2.


Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of input contains the Integer ‘n’.


Output Format:
The output contains an integer denoting the square root of ‘n’.


Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1:
6
Sample Output 1:
2
Explanation of Sample Input 1:
The square root of the given number 6 lies between 2 and 3, so the floor value is 2.
Sample Input 2:
100
Sample Output 2:
10
Explanation of Sample Output 2:
The square root of the given number 100 is 10.
Expected Time Complexity:
Try solving this in O(log(n)).
Constraints:
0 <= n <= 10 ^ 9

Time Limit: 1 sec.
Hint

Continue incrementing the number until the square of that number is greater than the given number.

Approaches (2)
Brute Force

The idea is to iterate through all numbers and check.

 

Algorithm :

 

  • Take care of the corner case, N = 0.
  • Take a variable ‘ans’ that stores the square root of the given number, initialize it to 1.
  • Run a loop while the square of ‘ans’ is less than or equal to the given number ‘N’.
    • Increment ‘ans’ by 1.
  • Return ‘ans’-1.
Time Complexity

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’) ).

Space Complexity

O(1)

 

We are not using any extra space.

Code Solution
(100% EXP penalty)
Square Root of a number
Full screen
Console