Given an integer X, find its square root. If X is not a perfect square, then return floor(√x).
Examples:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2.Input: x = 11
Output: 3
Explanation: The square root of 11 lies in between 3 and 4 so floor of the square root is 3.
Python Program to Find the Square Root
To find the floor of the square root, try with all-natural numbers starting from 1. Continue incrementing the number until the square of that number is greater than the given number.
Follow the steps below to implement the above idea
- Create a variable (counter) i and take care of some base cases, (i.e when the given number is 0 or 1).
- Run a loop until i*i <= n, where n is the given number. Increment i by 1.
- The floor of the square root of the number is i – 1
Below is the implementation of the above approach:
Python3
# Python3 program to find floor(sqrt(x)# Returns floor of square root of xdef floorSqrt(x): # Base cases if (x == 0 or x == 1): return x # Starting from 1, try all numbers until # i*i is greater than or equal to x. i = 1 result = 1 while (result <= x): i += 1 result = i * i return i - 1# Driver Codex = 11print(floorSqrt(x)) |
3
Complexity Analysis:
- Time Complexity: O(√X). Only one traversal of the solution is needed, so the time complexity is O(√X).
- Auxiliary Space: O(1).
Square root an integer using Binary search
The idea is to find the largest integer i whose square is less than or equal to the given number. The values of i * i is monotonically increasing, so the problem can be solved using binary search.
Below is the implementation of the above idea:
- Base cases for the given problem are when the given number is 0 or 1, then return X;
- Create some variables, for storing the lower bound say l = 0, and for the upper bound r = X / 2 (i.e, The floor of the square root of x cannot be more than x/2 when x > 1).
- Run a loop until l <= r, and the search space vanishes
- Check if the square of mid (mid = (l + r)/2 ) is less than or equal to X, If yes then search for a larger value in the second half of the search space, i.e l = mid + 1, update ans = mid
- Else if the square of mid is more than X then search for a smaller value in the first half of the search space, i.e r = mid – 1
- Finally, Return the ans
Below is the implementation of the above approach:
Python3
# Python 3 program to find floor(sqrt(x)# Returns floor of square root of xdef floorSqrt(x): # Base cases if (x == 0 or x == 1): return x # Do Binary Search for floor(sqrt(x)) start = 1 end = x//2 while (start <= end): mid = (start + end) // 2 # If x is a perfect square if (mid*mid == x): return mid # Since we need floor, we update # answer when mid*mid is smaller # than x, and move closer to sqrt(x) if (mid * mid < x): start = mid + 1 ans = mid else: # If mid*mid is greater than x end = mid-1 return ans# driver codex = 11print(floorSqrt(x)) |
3
Complexity Analysis:
- Time Complexity: O(log(X)).
- Auxiliary Space: O(1).
Square root an integer using built-in functions
Below is the implementation for finding the square root using the built-in function.
Python3
def countSquares(x): sqrt = x**0.5 result = int(sqrt) return resultx = 9print(countSquares(x)) |
3
Time Complexity: O(log(X))
Auxiliary Space: O(1)
Square Root Of Given Number using numpy.sqrt()
To find the square root of a number using Numpy, you can use the numpy.sqrt() function. This function takes in a number or an array of numbers and returns the square root of each element.
Here is an example of how you can use numpy.sqrt() to find the square root of a number:
Python3
import numpy as np# Find the square root of 9sqrt_9 = np.sqrt(9)print(sqrt_9) # Output: 3.0# Find the square root of a list of numbersnumbers = [4, 9, 16, 25]sqrt_numbers = np.sqrt(numbers)print(sqrt_numbers) # Output: [2.0 3.0 4.0 5.0] |
Output:
3.0
[2. 3. 4. 5.]
Note that numpy.sqrt() returns a Numpy array if the input is an array, and a single value if the input is a single number.
Time Complexity: The time complexity of the np.sqrt() function is O(1) for a single input and O(n) for an array of inputs, because it involves computing the square root of the input values. The time complexity is constant for a single input and linear in the size of the array for an array of inputs.
Space Complexity: The space complexity of the np.sqrt() function is O(1) for both a single input and an array of inputs, because it does not use any additional data structures and the space it uses is independent of the input size. The function returns a single value for a single input and an array of values for an array of inputs.
There can be many ways to solve this problem. For example, the Babylonian Method is one way. Please refer complete article on the Square root of an integer for more details!
