CHEATING DEVELOPER vs Log n Engineer on Sqrt(x), Leetcode 69

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[georgeyoung]

The real answer is to push back on the requirements and ask the business why you’re not allowed to use built in functions

[ycombine]

Congratulations! You did it. You’re hired. Now go build this basic CRUD app where you’ll never have to solve a problem like that again.

[mment]

Love how the "better" solution is 1ms slower xD

[YDtheFoo]

While binary search is straightforward and easy to implement, it converges relatively slowly compared to other methods. Modern programming languages typically use variations of the Newton-Raphson and Babylonian methods, which have better time complexity for finding square roots.

[sergokovaltsov]

Please, don't implement binary search like in this video.

1. Use M = L + (R - L) / 2 to avoid integer overflows (python saves him here but other languages won't)

2. Use < instead of <= to avoid infinite loop and off-by one errors. (It's can be considered as general advice to use < over <= when possible, read up about fencepost error and why semi-intervals is a good thing)

3. To the same point of semi-intervals. Imagine splitting your domain as 2 chunks [L, M) and [M, R). Then depending on the condition it's easy to determine how to update left and right boundaries.

left = M + 1 or right = M.

With following these tips you should be pretty much OK 99% of the time (not sure)

Binary search is simple but not easy. Be mindful. Or even better, check how to write it *correctly* in some article

[programming.jesus]

most insane square root impl I have ever seen in my life

[davidgillies]

Find highest bit set with int.bit_length(). Left shift 1 half this many bits as initial value. A couple of rounds of Newton-Raphson and cast as int

[vorkutavorkutlag]

For numbers bigger than 2, the square root is always smaller than half of the number

[EternityUnknown]

Bad solution: Expedient
Good solution: 6x development time for decreased performance

[angelll.]

what's cool is this is actually how you're taught to approximate square roots by hand in school :)

[mukundayyalasomayajula]

wait isn't this just assuming that x is a perfect square? cause he never set a condition to stop it from just alternating between two integers forever

[zb]

just loop i -= (i*i-x)/(2*i) until the floor of it doesn’t change, x being the number to find the sqrt of

[dneary]

I think you can LUT this for initial guesses for (say) the 4 most significant bits, then use one iteration of Newton-Raphson. You basically use an intial guess that is floor(sqrt(n) + 1/2) for n = 1 to 16. All integers should converge within 2 iterations to the right integer, I believe. In rough pseudocode:
* Verify n>0
Initialize x_1 = 1, x_2 = 2, x_0;
int LUT[] = {1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4};
index = n bitshifted 2k bits until it is less than or equal to 16
x_0 (initial guess for sqrt(n)) = LUT[index]<<k
while (x_1 != x_2) {
x_1 = floor(x_0/2 + n/(2*x_0));
x_2 = floor(x_1/2 + n/(2*x_1));
x_0 = x_2;
}

This should complete in 1 iteration for almost all integers. Although having attempted it, you need to be early with the rounding of integer types in the estimate, you can end up with x_1 and x_2 cycling between (n-1) and n for inputs of n^2-1.

[nolanrata]

A few other potential solutions:
- implement a fast square root algorithm based on the well-known fast inverse square root
- write the solution in C using inline ASM

[dimanarinull]

I did the same on floats using the archimedian(I think) formula for finding a square root, added sanity checks, and loop limits, but it usually returns naturally and was relatively fast.

[reishinsama]

Did this

def closest_sqrt(x):
for n in range(1, x):
if n * n == x:
return n
elif n * n > x:
if x - n * n > x - (n-1) * (n-1):
return n
else:
return n-1

Nice exercising

[calebkirschbaum]

You can do it close to constant time by doing the manual method of calculating sqrt. Off the top of my head it's something like pick an reasonable x(typically 1/2 of the value). Then your new value is x2=(n/(x1*x1))*x1 or something like that. Repeat until x2-x1 < 0.5.

To get the floor/ceil, try the bounds(x+-0.5) and check which of the 2 numbers is less than or equal to the n, and which is over.

[declanmoore]

I find that if you're limited to 32-bit integers, it can be faster to compute the square root as though you were doing it by hand. Algorithm would be O(n) for n-bit integers though. Optimized assembly for this reduced range can give good results though :)

[LePhenixGD]

Nice, not just for the number of the LeetCode question but also for your solution!

Wasn't aware that to compute the square root we'd have to use something as basic as a binary search! You made me learn something new today!