Sqrt(x)
LeetCode #69 · Easy · Math · C++ solution with worked-out approach and complexity analysis.
Approach
Linear Search
Strategy
- 1Handle base cases: if x is 0 or 1, return x.
- 2Iterate starting from i = 1.
- 3Check if i * i is equal to x. If so, return i.
- 4Check if i * i is greater than x. If so, the floor sqrt is i - 1.
- 5Use 'long' for the loop variable to prevent overflow during
Time
O(sqrt(x))
Space
O(1)
Problem description(from LeetCode)
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.
Examples
Example 1
- Input:
- x = 4
- Output:
- 2
- Note:
- 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^31 - 1
C++ Solution
solution.cpp
class Solution {
public:
int mySqrt(int x) {
if (x <= 1) return x;
long i;
for (i = 1; i * i <= x; i++) {
if (i * i == x) return i;
}
return i - 1;
}
};