0% completed
Problem Statement
Given a non-negative integer x
, return the square root of x
rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator. For example, do not use pow(x, 0.5)
in C++ or x ** 0.5
in Python.
Example 1:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.8284, and since we need to return the floor of the square root (integer), hence we returned 2.
Example 2:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2.
Example 3:
Input: x = 2
Output: 1
Explanation: The square root of 2 is 1.414, and since we need to return the floor of the square root (integer), hence we returned 1.
Constraints:
- 0 <= x <= 2<sup>31</sup> - 1
Solution
We can use a Binary Search approach to calculate the square root of an integer x
without using any in-built sqrt function.
For any integer x
, the square root of x
will lie between 0 and x/2
(inclusive) for x > 2
. Therefore, we can efficiently use binary search within this range to find the integer part of the square root (i.e., the floor value). By narrowing down the potential values step-by-step, binary search allows us to determine the largest integer y
such that y*y
is less than or equal to x
.
This approach ensures an efficient and accurate computation of the square root, especially for large values of x
, due to the logarithmic nature of binary search.
Step-by-Step Algorithm
- Handle Base Cases: If
x
is less than 2, returnx
directly (since the square root of 0 is 0, and the square root of 1 is 1). - Initialize Pointers: Set
left
to 2 andright
tox / 2
. - Binary Search Loop:
- While
left
is less than or equal toright
:- Calculate
mid
asleft + (right - left) // 2
. - Calculate
num
asmid * mid
. - If
num
is greater thanx
, moveright
tomid - 1
. - If
num
is less thanx
, moveleft
tomid + 1
. - If
num
equalsx
, returnmid
.
- Calculate
- While
- Return Result: Return
right
as the integer part of the square root ofx
.
Algorithm Walkthrough
Let's consider the input n = 8:
-
Initialize:
- Input
x = 8
. - Since
x
is not less than 2, proceed to the next step. - Set
left = 2
andright = 4
(8 // 2
).
- Input
-
First Iteration:
- Calculate
mid = 2 + (4 - 2) // 2 = 3
. - Calculate
num = 3 * 3 = 9
. - Since
num
(9) is greater thanx
(8), moveright
tomid - 1 = 2
.
- Calculate
-
Second Iteration:
- Now
left = 2
andright = 2
. - Calculate
mid = 2 + (2 - 2) // 2 = 2
. - Calculate
num = 2 * 2 = 4
. - Since
num
(4) is less thanx
(8), moveleft
tomid + 1 = 3
.
- Now
-
End Loop:
- Now
left = 3
andright = 2
. - Since
left
(3) is greater thanright
(2), exit the loop.
- Now
-
Return Result:
- Return
right = 2
as the integer part of the square root ofx = 8
.
- Return
Code
Here is the code for this algorithm:
Complexity Analysis
Time Complexity
-
Binary Search Algorithm: The key part of this algorithm is the binary search, which repeatedly divides the search interval in half. The time complexity of binary search is O(log n), where n is the size of the search space. In this case, the search space is initially from
2
tox/2
. -
Search Space: The maximum size of the search space is
x/2
(when x \geq 4). For smaller values ofx
, the function immediately returnsx
, as it's either0
or1
. -
Overall Time Complexity: Considering the binary search on a range up to
x/2
, the time complexity is O(log(x/2)), which simplifies to O(\log x).
Space Complexity
-
Constant Extra Space: The algorithm uses a fixed number of integer variables (
left
,right
,pivot
,num
), regardless of the input size. -
No Recursive Calls or Dynamic Allocation: The implementation does not use recursion or allocate additional data structures that grow with the input size.
-
Overall Space Complexity: Given the constant amount of extra space, the space complexity is O(1), meaning it's constant.
Table of Contents
Problem Statement
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity