Python Program To Find Square Root Of Given Number - Coding

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 x
 
 
def 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 Code
x = 11
print(floorSqrt(x))

Output

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 x
 
 
def 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 code
x = 11
print(floorSqrt(x))

Output

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 result
 
 
x = 9
print(countSquares(x))

Output

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 9
sqrt_9 = np.sqrt(9)
print(sqrt_9)  # Output: 3.0
 
# Find the square root of a list of numbers
numbers = [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!

Reffered: https://www.geeksforgeeks.org

Python Programs

Related
Python Program to print the pattern 'G'
Python Program to calculate Profit Or Loss
Python Program for Convert characters of a string to opposite case
Python Program for Remove leading zeros from a Number given as a string
Python Program to find if a character is vowel or Consonant

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	14