Solving a Leetcode problem daily — Day 8 | Sqrt(x) | by Subhradeep Saha | May, 2024 | Medium
Subhradeep Saha ・ May 7, 2024 ・
Medium
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:
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 of x is always ≤ x/2
By 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 input x
Code Implementation
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 x is 0, it returns 0 (square root of 0 is 0).
If x is 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 to x / 2 (considering the largest possible square root for the given x).
m (middle index) will be used during the search.
Binary Search Loop:
A while loop iterates as long as l is less than or equal to h. This ensures the search space keeps narrowing down.
Inside the loop:
m is calculated as the middle index between l and h — m is calculated indirectly to prevent integer overflow due to l + h
prod is calculated by squaring the m value, but using long to prevent integer overflow for larger values of x.
If prod is equal to x, it means we’ve found the exact square root, and the loop terminates, returning m.
Value Comparison and Search Refinement:
If prod is greater than x, it indicates the middle value (m) is too high. The upper bound (h) is updated to m – 1 to focus the search on the lower half of the range.
If prod is less than x, it indicates the middle value (m) is too low. The lower bound (l) is updated to m + 1 to 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 h is returned.
Now, why do we specifically return hand not l, 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 of x.
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 x is not 0 or 1, the code proceeds.
Initialization:
l is set to 1.
h is set to 4(half of 2).
m is not yet calculated
3. Iteration 1:
m is calculated as 1 + (4 — 1)/2 = 2.
prod is calculated as 2 * 2 = 4.
Since prod is less than x, l is updated to m + 1 (which becomes 3).
4. Iteration 2:
l = 3 is still less than h= 4
m is calculated as 3 + (4 — 3)/2 = 3.
prod is calculated as 3 * 3 = 9.
Since prod is greater x, h is updated to m — 1 = 2
4. Iteration 3:
l = 3 is now greater than h = 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 —
https://medium.com/@subhradeep_saha/solving-a-leetcode-problem-daily-day-4-add-binary-24a98c1df7c5
https://medium.com/@subhradeep_saha/solving-a-leetcode-problem-daily-day-2-plus-one-a77a96759794
