Sqrt(x) LeetCode Solution | Approaches in C++/Java/Python
Problem Description:
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.
Examples:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
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:
0 <= x <= 2³¹ - 1
Brute Force Approach:
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
We need to find the square root of a number x, rounded down to the nearest integer, without using any built-in functions. To approach this problem, let’s both perfect squares and non-perfect squares. It’s simple and systematic.
First, observe that x 1 to x. For instance, the square root of 4 is 2, which lies in the range 1 to 4. Similarly, the square root of 9 is 3, which lies in the range 1 to 9. Even the square root of 1 is 1, which lies in the range 1 to 1. This observation helps us limit the range we need to search within.
One straightforward solution is to traverse through the range 1 to x, square each number, and check which number satisfies y² = x. If we find such a number y, that’s the square root of x, and we can return y.
But what happens if x is not a perfect square? In this case, there will be no integer y such that y² = x. For example, if x = 8, there’s no integer whose square is exactly 8. To handle this, we can look for the smallest integer y such that y² > x, and then subtract 1. This gives us the integer part of the square root of x. For x = 8, 3² = 9 is slightly more than 8, so we subtract 1 to get 2, which is the integer square root of 8 rounded down.
By following this process, we can effectively handle both perfect squares and non-perfect squares. It’s simple and systematically greater ensures we stay within the constraints of not using built-in functions.
Let's understand with an example:
Let’s dry run the solution for x = 12:
- Start with y = 1.
Check: y² = 1² = 1
1 ≤ 12, so continue. - Increment y = 2.
Check: y² = 2² = 4
4 ≤ 12, so continue. - Increment y = 3.
Check: y² = 3² = 9
9 ≤ 12, so continue. - Increment y = 4.
Check: y² = 4² = 16.
16 > 12, so stop. - Return y−1 = 4−1 = 3.
The integer square root of 12, rounded down, is 3.
How to code it up:
Here are the concise steps to code the solution:
- Define a Function: Create a function mySqrt that takes an integer x as input.
- Initialize a Variable: Start a variable i at 1 to iterate over potential square roots.
- Iterate Using a Loop: Use a while loop to check if i² ≤ x. If true, increment i.
- Break the Loop: Stop when i² > x, as we’ve gone beyond the square root.
- Return Result: Return i - 1, which is the largest integer whose square is less than or equal to x.
- Handle Overflow (Optional): Use long long for i to handle edge cases like large values of x.
Code Implementation
1. Sqrt(x) Leetcode Solution C++ Try on Compiler
class Solution {
public:
int mySqrt(int x) {
// Use long long to avoid overflow for large values of x
long long i = 1;
// Loop until i^2 exceeds x
while (i * i <= x) {
// Increment i
i++;
}
// Return the integer whose square is the largest value less than or equal to x
return i - 1;
}
};
2. Sqrt(x) Leetcode Solution Java Try on Compiler
class Solution {
public int mySqrt(int x) {
// Use long to avoid overflow for large values of x
long i = 1;
// Loop until i^2 exceeds x
while (i * i <= x) {
// Increment i
i++;
}
// Return the integer whose square is the largest value less than or equal to x
return (int)(i - 1);
}
}
3. Sqrt(x) Leetcode Solution Python Try on Compiler
class Solution:
def mySqrt(self, x):
# Use a long type for large values (Python handles big integers automatically)
i = 1
# Loop until i^2 exceeds x
while i * i <= x:
# Increment i
i += 1
# Return the integer whose square is the largest value less than or equal to x
return i - 1
4. Sqrt(x) Leetcode Solution Javascript Try on Compiler
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
// Use a variable i to avoid overflow for large values of x
let i = 1;
// Loop until i^2 exceeds x
while (i * i <= x) {
// Increment i
i++;
}
// Return the integer whose square is the largest value less than or equal to x
return i - 1;
};Time Complexity: O(√x)
Let's do the time complexity analysis of sqrt(x) solution:
- The loop runs as long as i² ≤ x, and i starts at 1 and increments by 1 each time.
- The loop will continue until i² > x, so at the point where the loop stops, we have: i² > x
- Taking the square root of both sides: i > √x
- This means that the value of i will reach approximately √x before the condition i² ≤ x is no longer satisfied.
- Therefore, the number of iterations the loop executes is roughly proportional to √x , because i increments by 1 in each step and stops when it exceeds the square root of x.
Thus, the time complexity of this approach is O(√x).
Space Complexity: O(1)
Auxiliary Space Complexity: O(1 )
Explanation: We are only using a single variable i to store the current value. No additional data structures are used, and no arrays or lists are involved.
Thus, the auxiliary space complexity is O(1), as we only need a constant amount of space to store i.
Total Space Complexity: O(n)
Explanation: The input is x, which is an integer. An integer in most programming languages typically requires O(1) space.
Therefore, the total space used by the algorithm is O(1).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(√x), which is much more efficient. This means that for each test case, where x is at most 2³¹ - 1 (the upper limit for 32-bit integers), the solution executes in a reasonable amount of time even for large inputs.
Since O(√x) results in a maximum of approximately 46,340 operations (for x = 2³¹ - 1), the solution is efficient enough for values of x up to the given limit.
In competitive programming environments, problems generally handle up to 10⁶ operations per test case. With O(√x), the solution comfortably fits within these limits, even for the largest possible input values.
Therefore, the O(√x) time complexity ensures that the solution works efficiently within the problem constraints and will not result in Time Limit Exceeded (TLE) errors for values of x up to 2³¹ - 1, even when multiple test cases are involved
Can we optimize it?
Let's look at how we can optimize the solution further.
In our previous solution, we iterated over all values in the range [1, x] until we found the square root of x, which resulted in O(√x) time complexity. Now, we want to make this process more efficient.
Since we know the square root of x will always lie in the range [1, x], we can use this information to optimize our search. Specifically, if we consider an integer y in the range [1, x] as the square root of x, we know a few key things:
- Any number greater than y will always satisfy a * a < x.
- Any number b greater than y will always satisfy b * b > x.
For example, if x = 4, the square root is y = 2, and for numbers less than 2 (e.g., 1), 1 * 1 < 4, and numbers greater than 2 (e.g., 3), 3 * 3 > 4.
With this in mind, we can now use a more efficient approach.
Yes, you're right. You can use binary search.
To apply binary search, we should make sure that these three conditions satisfy:
- The data structure must be sorted:
In the square root problem, the "data structure" is the range of numbers from 1 to x. This range is inherently sorted in ascending one-half as numbers increase sequentially from 1 to x.
Why it satisfies: Since the range is sorted, we can confidently divide the range into two halves and determine in which half the square root might lie. - The middle element should help minimize or maximize the search space:
The middle element, calculated as mid = low + (high - low) / 2, serves as a pivot. By comparing mid * mid with x, we determine whether:
The square root is in the left half of the range (if mid * mid > x, we reduce the range to [low, mid - 1]).
The square root is in the right half of the range (if mid * mid < x, we reduce the range to [mid + 1, high]).
In every iteration, the comparison between mid * mid and x effectively minimizes the search space by discarding half of the range.
Why it satisfies: The middle element comparison ensures we are narrowing down the range by eliminating irrelevant parts of the search space, bringing us closer to the square root. - The search space must be monotonic:
The search space in the square root problem exhibits a monotonic property:
If mid * mid < x, the square root must lie in the range [mid + 1, high], as larger numbers have larger squares.
If mid * mid > x, the square root must lie in the range [low, mid - 1], as smaller numbers have smaller squares.
This monotonic behavior guarantees that if we rule out on of the range, the target cannot exist in that discarded portion.
Why it satisfies: The property that larger numbers have larger squares and smaller numbers have smaller squares ensures that the search space behaves monotonically, allowing binary search to work effectively.
The idea is simple. We have the range [1, x], so we will set low = 1 and high = x. We then pick the middle element in the range [1, x] and check the following:
- If mid * mid > x, then the square root y must be on the left side of mid, i.e., the range [1, mid - 1].
- If mid * mid < x, then the square root y must be on the right side of mid, i.e., the range [mid + 1, x].
- If mid * mid == x, then mid is the square root of x, and we can return mid.
By continually halving the range based on the comparison of mid * mid with x, we reduce the search space efficiently and find the square root.
When x is not a perfect square:
When x is not a perfect square, the binary search loop will not find an exact match where mid * mid == x. Instead, the loop will continue narrowing down the search range by adjusting the values of low and high. Eventually, the loop will terminate when low becomes greater than high, indicating that all possible values for mid have been exhausted.
At this point, high represents the largest integer whose square is still less than or equal to x. This is important because, even though x is not a perfect square, we still need the greatest whole number (integer) whose square is less than or equal to x.
For example:
- If x = 8, the square root is approximately 2.828, but we want the largest integer that, when squared, doesn’t exceed 8. The largest integer that works here is 2 because 2 * 2 = 4, which is less than 8, but 3 * 3 = 9, which is greater than 8.
So, when the loop ends, high will be the correct number to return. It gives us the largest integer whose square is less than or equal to x, which is exactly what we need when the square root isn’t a whole number. This value of high is effectively the "integer square root" of x, rounded down.
To sum it all up:
We will maintain two pointers: low = 1 and high = x to cover the range of possible square roots.
- Find the mid value: The mid value is calculated as mid = low + (high - low) / 2.
- Check if mid is the square root: If mid * mid == x, return mid as the square root of x.
- If mid * mid > x: This means the square root must lie to the left of mid, so we update high = mid - 1.
- If mid * mid < x: This means the square root must lie to the right of mid, so we update low = mid + 1.
- Termination: Continue this process until we don't find the square root or until low > high.
- When low > high indicates that x is not a perfect square, so return high. high will be the largest integer whose square is less than or equal to x, which is effectively the integer square root of x.
This binary search approach significantly improves the time complexity from O(√x) to O(log x), making it much faster, especially for large values of x.
Understand with an example:
Let's perform a concise dry run of the binary search approach for x = 12.
Initial Range:
low = 1, high = 12
Iteration 1:
mid = (1 + 12) / 2 = 6
6 * 6 = 36 which is greater than 12, so adjust high = mid - 1 = 5.
Iteration 2:
low = 1, high = 5
mid = (1 + 5) / 2 = 3
3 * 3 = 9 which is less than 12, so adjust low = mid + 1 = 4.
Iteration 3:
low = 4, high = 5
mid = (4 + 5) / 2 = 4
4 * 4 = 16 which is greater than 12, so adjust high = mid - 1 = 3.
Termination:
low = 4, high = 3
The loop ends as low > high.
Result: We return high = 3 because 3 * 3 = 9, which is the largest integer whose square is less than or equal to 12.
Final Answer: The integer square root of 12 is 3.
How to code it up?
Here are concise and generic steps to code the solution:
- Initialize Boundaries:
Set the low boundary to 1 (since the square root is always at least 1).
Set the high boundary to x (the square root can never be greater than x). - Binary Search Loop:
While low ≤ high, repeat the following steps. - Calculate Middle Element:
Compute mid = low + (high - low) / 2 to avoid overflow. - Check Square of Mid:
Calculate square = mid * mid (convert to long long to handle large numbers). - Check if Mid is the Exact Square Root:
If square == x, return mid as it is the exact square root. - Adjust Boundaries:
If square < x, update low = mid + 1 (search in the right half).
If square > x, update high = mid - 1 (search in the left half). - Return the Largest Integer:
When the loop ends (low > high), return high because it is the largest integer whose square is less than or equal to x.
Code Implementation
1. Sqrt(x) Leetcode Solution C++ Try on Compiler
class Solution {
public:
int mySqrt(int x) {
// Initialize the search range: low = 1, high = x
int low = 1;
int high = x;
// Perform binary search to find the square root
while (low <= high) {
// Calculate the middle value to avoid overflow
int mid = low + (high - low) / 2;
// Calculate the square of mid, using long long to handle large values
long long square = (long long)mid * mid;
// If mid squared equals x, we've found the square root
if (square == x) {
return mid;
}
// If mid squared is less than x, the square root is in the right half
else if (square < x) {
low = mid + 1;
}
// If mid squared is greater than x, the square root is in the left half
else {
high = mid - 1;
}
}
// If we don't find an exact match, return the largest integer whose square is less than or equal to x
return high;
}
};
2. Sqrt(x) Leetcode Solution Java Try on Compiler
class Solution {
public int mySqrt(int x) {
// Initialize the search range: low = 1, high = x
int low = 1;
int high = x;
// Perform binary search to find the square root
while (low <= high) {
// Calculate the middle value to avoid overflow
int mid = low + (high - low) / 2;
// Calculate the square of mid, using long to handle large values
long square = (long) mid * mid;
// If mid squared equals x, we've found the square root
if (square == x) {
return mid;
}
// If mid squared is less than x, the square root is in the right half
else if (square < x) {
low = mid + 1;
}
// If mid squared is greater than x, the square root is in the left half
else {
high = mid - 1;
}
}
// If we don't find an exact match, return the largest integer whose square is less than or equal to x
return high;
}
}
3. Sqrt(x) Leetcode Solution Python Try on Compiler
class Solution:
def mySqrt(self, x):
# Initialize the search range: low = 1, high = x
low = 1
high = x
# Perform binary search to find the square root
while low <= high:
# Calculate the middle value to avoid overflow
mid = low + (high - low) // 2
# Calculate the square of mid, using long to handle large values
square = mid * mid
# If mid squared equals x, we've found the square root
if square == x:
return mid
# If mid squared is less than x, the square root is in the right half
elif square < x:
low = mid + 1
# If mid squared is greater than x, the square root is in the left half
else:
high = mid - 1
# If we don't find an exact match, return the largest integer whose square is less than or equal to x
return high
4. Sqrt(x) Leetcode Solution Javascript Try on Compiler
var mySqrt = function(x) {
// Initialize the search range: low = 1, high = x
let low = 1;
let high = x;
// Perform binary search to find the square root
while (low <= high) {
// Calculate the middle value to avoid overflow
let mid = low + Math.floor((high - low) / 2);
// Calculate the square of mid, using a large integer check
let square = BigInt(mid) * BigInt(mid);
// If mid squared equals x, we've found the square root
if (square === BigInt(x)) {
return mid;
}
// If mid squared is less than x, the square root is in the right half
else if (square < BigInt(x)) {
low = mid + 1;
}
// If mid squared is greater than x, the square root is in the left half
else {
high = mid - 1;
}
}
// If we don't find an exact match, return the largest integer whose square is less than or equal to x
return high;
};
Time Complexity: O(log x)
Let's do the time complexity analysis of sqrt(x) solution:
We initialize two variables: low = 1 and high = x, which are used to define the search range for the square root.
In each iteration of the while loop, we calculate the middle point mid = low + (high - low) / 2 and check if the square of mid is greater than, less than, or equal to x.
Depending on the comparison, we adjust the low or high boundaries, effectively halving the search space at each step.
The key to understanding the time complexity is how many times the search range is halved. Initially, the range is from 1 to x. In the next iteration, the range is reduced to half, and so on.
After k iterations, the search space will be reduced to approximately x / 2ᵏ. We continue this process until the range is narrowed down to a single point.
To find the number of iterations, we set the condition low <= high, which terminates when low exceeds high. This occurs when the size of the range is reduced to 1, i.e., x / 2ᵏ = 1.
Solving for k:
x / 2ᵏ = 1 ⟹ 2ᵏ = x ⟹ k = log₂(x)
The loop runs O(log x) times. In each iteration, we perform constant-time operations (calculating mid, squaring mid, and comparing with x).
Thus, the overall time complexity is O(log x), where x is the input number for which we want to find the integer square root.
Space Complexity: O(1)
Auxiliary Space Complexity: O(1)
Explanation: The space complexity of this solution is O(1), because we only use a few variables (low, high, mid, square) to store intermediate results. No additional space is used that grows with the size of the input.
Total Space Complexity: O(1)
Explanation: The input is x, which is an integer. An integer in most programming languages typically requires O(1) space.
Therefore, the total space used by the algorithm is O(1).
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems.
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.You must write an algorithm with O(log n) runtime complexity.
A conveyor belt has packages that must be shipped from one port to another within days days.
The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.