Medium
Here is the Leetcode problem link — Sqrt(x)
Problem Statement
LeetCode presents a challenge where you’re given a non-negative integer x and the task is to write a function that returns the integer square root of x rounded down to the nearest whole number.
This calculation must be performed without relying on built-in functions like pow(x, 0.5) (C++) or x ** 0.5 (Python).
Example:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down
to the nearest integer, 2 is returned.
Constraints:
x can range from 0 to the maximum possible value for an integer data type (2^31 - 1).
High Level Approach
At first, the instinctive approach to solving the problem involves using a language’s built-in function to find the square root. However, this method does not align with the problem definition. The second apparent approach that comes to mind is finding the square root by iterating through every number from 1 to x. However, the most optimal solution, which we will discuss in this blog offers a more efficient approach.
The high-level concept of the optimal approach is as follows:
For any number
x, the square root ofxis always ≤x/2By employing binary search within the range of 1 to
x/2, we check whether the middle number is the square root or not. If not, we narrow down the search space for the next iteration by comparing the square of the middle number with the inputx
Code Implementation
class Solution {
public:
int mySqrt(int x) {
if (!x || x == 1) {
return x;
}
int l = 1, h = x / 2, m;
while (l <= h) {
m = l + (h - l) / 2;
long prod = (long) m * m;
if (prod == x) {
return m;
}
if (prod > x) {
h = m - 1;
} else {
l = m + 1;
}
}
return h;
}
};
Breakdown of the Code
This code defines a class Solution with a function mySqrt that takes the integer x as input and returns the integer square root rounded down.
Edge Case Handling:
The code first checks for edge cases:
If
xis 0, it returns 0 (square root of 0 is 0).If
xis 1, it returns 1 (square root of 1 is 1).
Binary Search Initialization:
Three integer variables are declared:
l(lower bound) initialized to 1.h(upper bound) initialized tox / 2(considering the largest possible square root for the givenx).m(middle index) will be used during the search.
Binary Search Loop:
- A
whileloop iterates as long aslis less than or equal toh. This ensures the search space keeps narrowing down.
Inside the loop:
mis calculated as the middle index betweenlandh— m is calculated indirectly to prevent integer overflow due tol + hprodis calculated by squaring themvalue, but usinglongto prevent integer overflow for larger values ofx.If
prodis equal tox, it means we've found the exact square root, and the loop terminates, returningm.
Value Comparison and Search Refinement:
If
prodis greater thanx, it indicates the middle value (m) is too high. The upper bound (h) is updated tom - 1to focus the search on the lower half of the range.If
prodis less thanx, it indicates the middle value (m) is too low. The lower bound (l) is updated tom + 1to search the upper half of the range.
Returning the Result:
We encounter two scenarios for returning the result:
The first occurs when we find the exact square root inside the while loop, leading to an immediate return.
In the second case, if we do not find the exact square root, the while loop terminates, and the value of
his returned.
Now, why do we specifically return
hand notl,m, or any other number?
The loop halts when l exceeds h, guaranteeing that his always one less than a number whose square root is greater than x. This ensures that we return the integer rounded down, as specified in the problem statement.
=> If the problem were to require returning the closest possible square root rounded up, we would return l instead of h.
=> Similarly, if the problem mandated returning -1 when an exact square root isn’t found, we would return -1instead of h.
Complexity Analysis
Time Complexity
The time complexity of the binary search solution for finding the integer square root is O(logn), where n is the input number x. Here's a breakdown of why:
Binary Search: The algorithm employs binary search, which repeatedly halves the search space with each iteration. This process of dividing the space ensures significant reduction in the number of comparisons needed to locate the target value.
Logarithmic Iterations: The number of iterations required to traverse the search space using binary search is roughly proportional to the logarithm of the initial search space size (base 2). In this case, the initial space ranges from 1 to
x / 2, which is logarithmic in terms ofx.
Therefore, the time complexity grows logarithmically with the increase in the input value x, making the solution efficient for handling larger numbers.
Space Complexity
The space complexity of the binary search solution is O(1), which is considered constant space complexity. Here’s why:
Limited Variables: The algorithm utilizes a fixed number of variables to store essential data like loop counters, indices, and temporary values. These variables do not depend on the input size
x.No Additional Data Structures: The solution doesn’t involve creating or manipulating any additional data structures like arrays or lists whose sizes would scale with the input.
Because the space complexity remains constant regardless of the input size, the solution is memory-efficient.
Dry Run with a Test Case
Let’s perform a dry run on the code using the example x = 8:
Edge Case Check: Since
xis not 0 or 1, the code proceeds.Initialization:
lis set to 1.his set to 4(half of 2).mis not yet calculated
3. Iteration 1:
mis calculated as1 + (4 — 1)/2 = 2.prodis calculated as2 * 2 = 4.Since
prodis less thanx,lis updated tom + 1(which becomes 3).
4. Iteration 2:
l= 3 is still less thanh= 4mis calculated as3 + (4 — 3)/2 = 3.prodis calculated as3 * 3 = 9.Since
prodis greaterx,his updated tom — 1= 2
4. Iteration 3:
-
l= 3 is now greater thanh= 2, so the while loop terminates now
5. Result: The function returns h (which is 2), representing the integer square root of 8 rounded down (as expected).
Real-World Applications
Finding the integer square root without built-in functions has various real-world applications:
Game Development: In video games, calculating distances, applying physics simulations, or generating random numbers can involve square root computations. Using an efficient custom implementation like this can be beneficial, especially for performance optimization in resource-constrained environments.
Cryptography: Some encryption algorithms rely on modular arithmetic operations, which might involve square root calculations. Implementing a custom square root function can provide more control over the algorithm’s behavior, potentially enhancing security.
Embedded Systems: In microcontrollers or other embedded systems with limited processing power and memory, using a custom square root function can be more efficient than relying on bulky libraries with built-in math functions.
Conclusion
This blog post delved into essential concepts such as square root constraints and the application of the binary search algorithm to address problems where search spaces can be minimized for subsequent iterations, thereby reducing time complexities from O(n) to O(logn). Grasping this approach can prove invaluable in scenarios demanding efficient square root calculations without dependence on external libraries.
References
Game Development with Physics: https://www.new3jcn.com/simulation.html
Introduction to Cryptography: https://www.khanacademy.org/computing/computer-science/cryptography
Introduction to Embedded Systems: https://www.amazon.com/Embedded-Systems-Architecture-Programming-Engineering/dp/007340456X
Diagrams in the Dry run section are created using Canva
Cover photo by Antoine Dautry on Unsplash
If you liked this post, do applaude by clicking on the clap hands icon and follow me https://medium.com/@subhradeep_saha for such posts. If you are a Maths + Coding enthusiast, then do checkout these Medium posts of mine solving other Leetcode problems related to Math and Arrays —
Top comments (0)