in this code snippet you don’t need to check for 0:
def square_root(n: int) → int:
left, right = 0, n
mid = -1
first_smaller_or_equal = -1
while left <= right:
mid = (left + right)//2
if mid**2 == n:
return mid
elif mid**2 < n:
first_smaller_or_equal = mid
left = mid + 1
else:
right = mid - 1
return first_smaller_or_equal
Why binary search when
def square_root(n: int) -> int:
return int(n ** .5)
does the trick?
IMO, if we change the feasible function to i^2 <=n, the code gets simpler as follow:
if (n == 0) return 0;
int left = 1;
int right = n;
int res = -1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(mid <= n / mid) {
res = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return res;
def square_root(n: int) → int:
def feasible(val):
return val**2
left, right = 0, n
current_root = -1
while left <= right:
mid = (left + right)//2
current_square = feasible(mid)
if current_square == n:
return mid
elif current_square > n:
right = mid - 1
else:
left = mid + 1
current_root = mid
return current_root
Not really using binary search but instead a math trick in Python:
def square_root(n: int) → int:
if n == 0 or n == 1:
return n
return int(n**0.5)
function squareRoot(n) {
if(n===0) return 0
let left = 1
let right = n
let first = 0
while(left<=right){
let mid = Math.floor((left+right)/2)
if(mid**2===n){
return mid
}else if(mid**2<n){
first = mid
left = mid + 1
}else{
right = mid - 1
}
}
return first
}
This is similar to my Java code as well, I’m wondering about flaws here or if this is less efficient than the solution?
public static int squareRoot(int n) {
int left = 0, sqRoot = n, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
int exp = mid * mid;
if (exp == n) return mid;
else if (exp < n) {
sqRoot = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return sqRoot;
}
I tested it with these values and they pass:
int[] approxSquares = {3, 8, 13, 18, 145, 119};
int[] perfectSquares = {0, 1, 4, 16, 64, 144, 169, 1089};
def square_root(n: int) → int:
start = 0
while start * start <= n:
start = start + 1
return start - 1
This was my result and I passed all of the testcases.
public static int squareRoot(int n) {
// WRITE YOUR BRILLIANT CODE HERE
float halfN = n/2;
float result = halfN * halfN;
if(result < n){
return n;
}
while(result > n){
halfN /= 2;
result = halfN * halfN;
}
halfN = Math.round(halfN);
return (int)halfN;
}
def square_root(n: int) -> int:
# WRITE YOUR BRILLIANT CODE HERE
if n == 0: return 0
l, r = 1, n
while l <= r:
mid = (l + r) // 2
if mid * mid == n:
return mid
elif mid * mid > n:
r = mid - 1
else:
l = mid + 1
return r
return 0
This passes all the test cases. Is there a problem with just returning the right-most bound after the while loop ends?
This solution may be more elegant:
def square_root(n: int) -> int:
# WRITE YOUR BRILLIANT CODE HERE
l, r = 0, n
last_index = -1
while l <= r:
mid = (l + r)//2
if mid*mid <= n:
last_index = mid
l = mid + 1
else:
r = mid - 1
return last_index
This is the solution I got as well.
I think it makes more sense mapping (mid*mid) <= n as “true” and finding the righmost “true” in the boolean mapping rather than what the explanation is saying
I recognize the overall goal here is to teach pattern recognition to quickly solve an algorithm, as in this case, recognizing that you can solve it by recycling the binary search solution. However, I wanted to point out you can optimize this solution by recognizing that for n >= 4, the square root will be less than half of n. In this case, we can add an extra check for when n = 1, and allow the logic of the while loop to correctly identify the square root of n = 2 and n = 3 rounds down to 1 when setting right to 1.
Spoiler Solution
function squareRoot(n) {
if (n === 0 || n === 1) return n;
let left = 1;
let right = Math.floor(n / 2);
let res = -1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (mid**2 === n) {
return mid;
} else if (mid**2 > n) {
res = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return res - 1;
}
Clean solution:
public static int squareRoot(int n) {
int l = 1, r = n;
while (l <= r) {
int mid = l + (r - l) / 2;
if (mid == n / mid) return mid;
else if ( mid > n / mid) r = mid - 1;
else l = mid + 1;
}
return r;
}
One more solution:
public static int squareRoot(int n) {
int left = 0, right = n, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid * mid == n) {
return mid;
} else if (mid * mid > n) {
right = mid - 1;
} else {
ans = mid;
left = mid + 1;
}
}
return ans;
}
what about negative number, the question does not specify +ve or -ve number. For negative number the solution will not work.( left, right = 0, abs(-8)) might work
Here is my solution using Repeated Subtraction Method
def square_root(n: int) -> int:
odd = 1
sr = 0
while n - odd >= 0:
n = n - odd
odd += 2
sr += 1
return sr
Can some one explain me why we follow binary search approach to get the Square root…
Absolutely agree!
The solution which provided on the website, looks more like a hack, then a real solution.
Especially the part
return res - 1;