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)) |
Output
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).
Python Program To Find Square Root Of Given Number
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.