Given an integer x, find the square root of x. If x is not a perfect square, then return floor(√x).
 
Example 1:
Input:
x = 5
Output: 2
Explanation: Since, 5 is not a perfect 
square, floor of square_root of 5 is 2.
Example 2:
Input:
x = 4
Output: 2
Explanation: Since, 4 is a perfect 
square, so its square root is 2.
 
Your Task:
You don't need to read input or print anything. The task is to complete the function floorSqrt() which takes x as the input parameter and return its square root.
Note: Try Solving the question without using the sqrt function. The value of x>=0.
 
Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ x ≤ 10^{7}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Mathematics

Complete search

Starter code: #User function Template for python3





#Complete this function

class Solution:

    def floorSqrt(self, x): 

    #Your code here

Solutions:
class Solution:

	def floorSqrt(self, x):
		st = 0
		en = x
		while st <= en:
			mid = (st + en) // 2
			if mid * mid == x:
				return int(mid)
			elif mid * mid < x:
				st = int(mid + 1)
			else:
				en = int(mid - 1)
		return int(en)


class Solution:

	def floorSqrt(self, x):
		for j in range(4000):
			if j ** 2 == x:
				return j
				break
			elif j ** 2 < x < (j + 1) ** 2:
				return j
				break


class Solution:

	def floorSqrt(self, x):
		low = 0
		high = x
		ans = float('-inf')
		while low <= high:
			mid = low + int((high - low) / 2)
			mid_sq = mid * mid
			if mid_sq == x:
				return mid
			elif mid_sq > x:
				high = mid - 1
			else:
				low = mid + 1
				ans = mid
		return ans


class Solution:

	def floorSqrt(self, x):
		(min_, max_) = (1, x)
		result = -1
		while min_ <= max_:
			mid = (min_ + max_) // 2
			mids_square = mid * mid
			if mids_square > x:
				max_ = mid - 1
			elif mids_square < x:
				(min_, result) = (mid + 1, mid)
			elif mids_square == x:
				return mid
		return result


class Solution:

	def floorSqrt(self, x):
		y = int(math.sqrt(x))
		return y


import math

class Solution:

	def floorSqrt(self, x):
		return math.floor(math.sqrt(x))


class Solution:

	def floorSqrt(self, x):
		a = 1
		while a * a <= x:
			a += 1
		return a - 1


import math

class Solution:

	def floorSqrt(self, x):
		ans = int(math.sqrt(x))
		return ans


class Solution:

	def floorSqrt(self, x):
		x1 = x ** (1 / 2)
		return int(x1)


class Solution:

	def floorSqrt(self, x):
		(l, r) = (1, x)
		while l <= r:
			mid = (l + r) // 2
			cur = mid * mid
			if cur == x:
				return mid
			elif cur < x:
				l = mid + 1
			else:
				r = mid - 1
		ans = int(x ** (1 / 2))
		return ans


class Solution:

	def floorSqrt(self, x):
		s = x ** (1 / 2)
		return int(s)


class Solution:

	def floorSqrt(self, x):
		return int(x ** 0.5)


class Solution:

	def floorSqrt(self, x):
		l = 1
		r = x
		while l <= r:
			mid = l + (r - l) // 2
			if mid * mid == x:
				return mid
			elif mid * mid < x:
				l = mid + 1
			else:
				r = mid - 1
		return r


class Solution(object):

	def power(self, power, num):
		val = 1
		for _ in range(power):
			val *= num
		return val

	def floorSqrt(self, x):
		(n, m) = (2, x)
		(left, right) = (1, m)
		while left <= right:
			mid = (left + right) // 2
			val = self.power(n, mid)
			if val == m:
				return mid
			elif val > m:
				right = mid - 1
			else:
				left = mid + 1
		return right


class Solution:

	def floorSqrt(self, x):
		if x == 0 or x == 1:
			return 1
		s = 1
		e = x
		ans = 0
		while s <= e:
			m = (s + e) // 2
			if m * m == x:
				return m
			elif m * m > x:
				e = m - 1
			else:
				s = m + 1
				ans = m
		return ans


class Solution:

	def floorSqrt(self, x):
		i = 1
		while i * i <= x:
			i += 1
		return i - 1


class Solution:

	def floorSqrt(self, x):
		number = int(x ** 0.5)
		if number * number == x:
			return number
		else:
			return number


class Solution:

	def floorSqrt(self, x):
		if x < 0:
			raise ValueError
		(low, high) = (0, x)
		while low <= high:
			mid = (low + high) // 2
			mid_sq = mid ** 2
			if mid_sq < x:
				low = mid + 1
			elif mid_sq > x:
				high = mid - 1
			else:
				return mid
		return high


class Solution:

	def floorSqrt(self, x):
		low = 0
		high = x
		while low <= high:
			mid = math.floor((low + high) / 2)
			sq = mid * mid
			if sq == x:
				return mid
			elif sq > x:
				high = mid - 1
			else:
				low = mid + 1
				ans = mid
		return ans


class Solution:

	def floorSqrt(self, x):
		low = 0
		high = x
		mid = (low + high) // 2
		ans = -1
		while low <= high:
			s = mid * mid
			if s == x:
				return mid
			if s < x:
				ans = mid
				low = mid + 1
			else:
				high = mid - 1
			mid = (low + high) // 2
		return ans


class Solution:

	def floorSqrt(self, x):
		(i, j) = (0, x)
		while i <= j:
			m = i + j >> 1
			if m * m == x:
				return m
			elif m * m < x:
				i = m + 1
			else:
				j = m - 1
		return j


import math

class Solution:

	def floorSqrt(self, x):
		y = math.sqrt(x)
		z = math.floor(y)
		return z


class Solution:

	def floorSqrt(self, x):
		(left, right) = (1, x)
		while left <= right:
			mid = (left + right) // 2
			if mid * mid == x:
				return mid
			elif mid * mid > x:
				right = mid - 1
			else:
				left = mid + 1
		return right


class Solution:

	def floorSqrt(self, x):
		low = 1
		high = x
		while low != high:
			mid = (low + high) // 2
			if mid * mid == x:
				return mid
			elif mid * mid > x:
				if high == mid:
					return mid
				high = mid
			else:
				if low == mid:
					return mid
				low = mid
		return 1


class Solution:

	def floorSqrt(self, x):
		s = 0
		e = x
		while s <= e:
			mid = (s + e) // 2
			if mid * mid == x:
				return mid
			elif mid * mid > x:
				e = mid - 1
			else:
				s = mid + 1
		return e


class Solution:

	def floorSqrt(self, x):
		for i in range(1, x + 1):
			if i * i == x:
				return i
			elif i * i > x:
				return i - 1


import math

class Solution:

	def floorSqrt(self, x):
		if x < 4:
			return 1
		s = 1
		e = x // 2
		mid = None
		while s <= e:
			mid = (s + e) // 2
			if mid * mid < x:
				s = mid + 1
			else:
				e = mid - 1
		if s * s <= x:
			return s
		else:
			return s - 1


class Solution:

	def floorSqrt(self, x):
		y = x ** 0.5
		z = int(y)
		return z


class Solution:

	def floorSqrt(self, x):
		if x == 0 or x == 1:
			return x
		start = 0
		end = int(x // 2)
		ans = 0
		while start <= end:
			mid = start + (end - start) // 2
			if mid * mid == x:
				return mid
			elif mid * mid < x:
				start = mid + 1
				ans = mid
			else:
				end = mid - 1
		return ans


class Solution:

	def floorSqrt(self, x):
		y = x ** (1 / 2)
		return int(y)


class Solution:

	def floorSqrt(self, x):
		l = 0
		h = x
		while l <= h:
			m = int(l + (h - l) / 2)
			if m * m == x:
				return m
			elif m * m < x:
				l = m + 1
			elif m * m > x:
				h = m - 1
		return h


class Solution:

	def floorSqrt(self, x):
		if x == 1 or 0:
			return x
		else:
			return int(x ** (1 / 2) // 1)


class Solution:

	def floorSqrt(self, x):
		num = 1
		while num * num <= x:
			num = num + 1
		return num - 1


import math

class Solution:

	def floorSqrt(self, x):
		l = int(math.sqrt(x))
		return l


import math

class Solution:

	def floorSqrt(self, x):
		l = 0
		h = x
		mid = (l + h) // 2
		while l <= h:
			if int(mid ** 2) == x:
				return int(mid)
			elif int(mid ** 2) > x:
				h = mid
			else:
				l = mid
			mid = (l + h) / 2


class Solution:

	def floorSqrt(self, x):
		l = 1
		if x < 4:
			return 1
		r = x
		mid = (r + l) // 2
		while l <= r:
			if mid * mid > x:
				r = mid - 1
			if mid * mid < x:
				l = mid + 1
			if mid * mid == x:
				return mid
			mid = (r + l) // 2
		return mid


class Solution:

	def floorSqrt(self, x):
		for i in range(1, int(x ** 0.5 + 1)):
			if i * i == x:
				return i
		y = int(x ** 0.5)
		return y


class Solution:

	def floorSqrt(self, x):
		temp = x // 2 + 1
		temp2 = 1
		while temp2 <= temp:
			if temp2 ** 2 <= x:
				temp2 += 1
			else:
				break
		return temp2 - 1


class Solution:

	def floorSqrt(self, x):
		if x == 1 or x == 0:
			return x
		ans = 1
		res = 1
		while res <= x:
			ans += 1
			res = ans * ans
		return ans - 1


class Solution:

	def floorSqrt(self, x):
		start = 1
		end = x // 2 + 1
		ans = -1
		while start <= end:
			mid = start + (end - start) // 2
			square = mid * mid
			if square == x:
				ans = mid
				break
			elif square > x:
				end = mid - 1
			else:
				ans = mid
				start = mid + 1
		return ans


import math

class Solution:

	def floorSqrt(self, x):
		if math.sqrt(x) == math.ceil(x):
			return int(math.sqrt(x))
		else:
			return math.floor(math.sqrt(x))


class Solution:

	def floorSqrt(self, x):
		import math
		n = x
		i = 0
		while i <= n:
			mid = (i + n) // 2
			if mid * mid == x:
				return mid
			elif mid * mid > x:
				n = mid - 1
			else:
				i = mid + 1
		if mid * mid > x:
			return mid - 1
		else:
			return mid


import math as m

class Solution:

	def floorSqrt(self, x):
		a = m.sqrt(x)
		return int(a)


class Solution:

	def floorSqrt(self, x):
		import math
		if int(x ** 0.5) == x ** 0.5:
			return int(x ** 0.5)
		return math.floor(x ** 0.5)


class Solution:

	def floorSqrt(self, x):
		y = 0
		while y * y <= x:
			y += 1
		return y - 1


import math

class Solution:

	def floorSqrt(self, x):
		if x == 0 or x == 1:
			return x
		start = 1
		end = x
		res = 0
		while start <= end:
			mid = (start + end) // 2
			if mid * mid == x:
				return mid
			if mid * mid < x:
				start = mid + 1
				res = mid
			else:
				end = mid - 1
		return res


import math

class Solution:

	def floorSqrt(self, x):
		ans = x ** 0.5
		return math.floor(ans)


class Solution:

	def floorSqrt(self, x):
		lo = 1
		hi = x
		while lo <= hi:
			mid = (lo + hi) // 2
			if mid * mid == x:
				return mid
			if mid * mid > x:
				hi = mid - 1
			else:
				lo = mid + 1
		return lo - 1