Microsoft Coding Interview Question - Valid Perfect Square - Leetcode 367

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[GregHogg]

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

[davidgillies]

Yeah, that's not going to scale. In practice you test whether the number is a quadratic residue mod a few small integers. The first stage is to look at the number mod 256 i.e. examine the least significant byte. Then, for a 64-bit machine, test mod 5, 7, 9, 13, 17 and 97. This catches 99.62% of perfect squares very quickly. If the number passes the test you still need to verify it's a square which is expensive, but you only have to do it 0.38% of the time

[LilSnotbag]

Perfect circles been real quiet since this one dropped

[shubhambhattacharjee]

You can also start the range as 1 to N/2, the sqrt can't be bigger thaan half of the number for any number >= 4. And we can always do a sqrt(n) == floor(sqrt(n)), but I guess that could have a rounding error.

[woutverjans]

Yes but you can make it scale better at the cost of a little bit of overhead.

1. Squares of even numbers are always even and squares of odd numbers are always odd. Don't check even numbers when getting the square root of 121 but only check the odd ones.

2. If you have some idea of what range most of the numbers you want to check are then don't begin at 1² (actually, never begin at 1, it's always 1). If needed make a list where the ends are the range of most of your numbers and fill the rest with other numbers that allow you to get closer in fewer steps. When your result is between 2 of the numbers in the list then you start checking more closely. Alternatively you can take steps of 10 and square those, of your number is more than 100 but less than 400 you know it's root is between 10 and 20.

Edit: 3. As someone else pointed out, you only need to check up to N/2 as the square can't be higher than that. But again, if you know your numbers are going to be large than you could try N/4 as any number larger than 4 would fall in that range.

[justinturbyfill]

square=sqrt(num)
floor = square//1
return square==floor
I did this in python and beat 97.3%

[TerjeMathisen]

This is simply taking the (integer) square root, something you can do very quickly with a ff1() (find-first-one) bitscan instruction to determine the approximate scale, then a lookup table to get the approximate answer before you use Newton-Raphson to either get the exact result or find that it isn't a square: Easily doable in well under 100 clock cycles for any unsigned integer of 64 bits or less.

[pieordie]

you can also do log base 2 to see if that is a int or a double.

[Vi]

Here's a question to everyone in the comments trying to optimise this further... Why?

This solution is logarithmic time, easy to understand, and involves simple instructions. Seeing all of the overcomplication in this comments section has me anxious about entering the industry.

[R_Y_Z_E_N]

Better approach use range from 1 to n/2 (make r= n/2 in this code at start) and do binary search

[sophiophile]

One optimization to the solution provided can be made by observing the fact that every number's square root has the property: # of digits in floor(sqrt(n)) = ceil (1/2 * # of digits in n).

Therefore, instead of starting at 1/2 of n, you can safely have a range between 100.... to 999.... where the numbers have 1/2 as many digits as n (rounding up).

For very small n, this won't help (but the process is really quick anyways). But for very large numbers, let's say you can start with a range of instead of

[devanshpatel]

Just take the square root of the number in integer and a double and subtract both of them and compare the last the digits after decimal and if the digits after decimal are greater than zero then there is some leftover so this is not a perfect square and hence you can solve this problem in constant time

[Ноунеймбезгалочки-мч]

remove the biggest even amount of zeroes from the right(store that as n), Babylonian square root till integer precision, return result<<n

[Kenshin]

The second method seems way longer than the first, but with small numbers it's easy to just do it in your head.

[angelosefstratiou]

Newton's method for solving the equation x^2 - y = 0. Could work as well and i believe it converges faster.

[xzayler]

Maybe it's dumb but you could lower the steps required in half if you check if the number is even or uneven. If it's even you know it can only be a square of even numbers. Similarly with an odd number.

So just check between 1 to another odd large number or from 2 to an even number. And set the boundaries as L+2 or R-2

[vinceguemat]

i think, while it's not a random number, it should be a faster algorithme than bin search... Maybe something with an approximation of log base 2 of n like counting the number of digit base 2 and half this quantity should give a good approximation

[rendor]

I just memorize the exponential table just like the multiplication table. That makes finding the square root feel like you're just dividing

[kaneeshkharran]

I expected a different type of comment section but this comment section is smarter than the whole youtube users 😅 bye

[pasischei]

just scream "HASHMAP!". That does the job