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
Serious question - where do you learn stuff like this? Had an algorithmic programming class in college but never had to solve problems like this on the job. At a bare minimum, this is fascinating.
@@jackhedaya571 Do you mean me or the channel owner? If you're asking me, then the answer is many, many years using computers to solve number theory problems (I'm not a mathematician, but a mathematically-oriented software engineer).
@@davidgillies620 Yup! Was asking you. Saw the question and immediately thought there needs to be a super fast way of doing it (I was guessing it would be some bit magic). That's really cool! Can I ask what domain of software you work in? My day-to-day is mostly APIs, DBs, deployments, etc. but a part of me yearns to work on problems that require more clever solutions.
Best way to scale this solution is to see that # of digits in the sqrt(n) is the ceiling of 1/2 the digits in n. Then you can set your binary search range to 10000....99999 (with the number of digits determined by the relation described above). This is true for 100% of cases, no exceptions.
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 1000000000, you can start with a range of 10000-99999 instead of 1-500000000.
Btw, I offer personalized 1 on 1 tutoring services for data structures and algorithms / coding interview prep - please email greg.hogg1@outlook.com to book a meeting with me!
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.
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.
I think I have one of the fastest leetcode solutions for this one iirc. I cheated and used a taylor series expansion that's done using type coercion in C++ as an initial guess.
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
It'd probably be much faster to find the number of digits in the representation of the value, and just drop half of them and start you search there. So if N = 405332, don't start with 202666, but with 405. A binary search takes 3 steps to remove a digit from a decimal representation, which could be a lot of steps for a very large number.
you can go from 1 to N/2 and check only those that have the same parity than N. that speeds it quite a bit for large numbers. there are other additional methods to speed it even more but are a bit more complex and it's late for me. good night.
In c++ its too easy, just create an int n, read n from console, calculate sqrt(n) - dont forget to include cmath, create a double variable m = sqrt(n) and of static cast m - n == 0 return true else return false
I am thinking that you can scale all recorded speeds for segments down to a range (0,1] where 1 * speed limit gives you the absolute speed. Also, featurize the historical timestamps into day of week/month, year, season, holiday, etc for those 2 min segments for each day. From this, there are plenty of regression models that are fast enough to be able to put out a (0,1] speed given the features for the actual predicted period/road segment. You can train these on splits with multiple 2 month holdouts to do as many sessions of cross-validation for hyperparameter tuning as you like. Your loss function can be MAE/RMSE/etc for the 2 months of predictions. Each day, you batch create your predictions for the next day, and they are stored in a fast cache to be used with the existing shortest path function to calculate the ETA.
@@GregHogg Woops. This comment was supposed to go on a MLSD video. Was wondering why it didn't show up. I'll post an actually relevant comment in a new thread haha.
If you take a look at the perfect squares you'll notice their progression is as follows: 4-1=3 9-4=5 16-9=7 25-16=9 ... Those are the odd numbers. So if you want to check if any number is a perfect square you can check if it's part of this progression or not.
If the sqrt is not allowed simply use the representation of a sqrt which will always be ^(1/2), by doing so and validating if the number is a int, it’ll beat that since its complexity is O(1)
Sqrt operation is not O(1). If i ask you what the sqrt of an arbitrary number is you would need to do an increasing amount of work proportional to the magnitude of the number I chose.
@@njgskgkensidukukibnalt7372 But we assume the size of integer if fixed, e.g. 32bit, 64bit. So the magnitude of a number is constant. Without the assumption, even the method shown in the video will need to handle large numbers, or integers with arbitrary number of bits.
@@user-wt1ul7ki6p ? i dont understand. The code in the video (and for an integer sqrt program) does a binary search between 0 and n. This will take O(logn). The number of bits needed to represent the number is independent of the number of steps the binary search part will take. What matters is the magnitude of n which is not constant here.
It boils down to there being no pure integer square root CPU instructions under the hood - the simplest is the x87 fsqrt function which yields a floating point result with only around ~23 bits of precision. The bottom line here is that you cannot rely on floating point values because it require equality testing which is non-deterministic due to the lack of precision. Even if you use SSE (32bits of precision) or SS2 (64 bits), this fundamental constraint applies - you cannot be guaranteed that you have enough precision to guarantee a "perfect" square root. You could of course implement an integer sqrt function (for example Newton's or Heron's method) to appeal to the "understandability" of what you're trying to achieve, but since it is iterative it has a non-linear cost, which happens to be greater than this recursive approach.
In theory it wouldn't work for all N. there could be some N that is close enough to a perfect square that the decimals get truncated after enough places after the sqrt. and int() will truncate any float its given so you'd have to do something else like modulo division to check for decimals.
@@bobmike2373 then u could, instead of int(), just modulo divise the sqrt to itself floored. To do so, u would store the result of the sqrt in a variable so that u don't have to calculate it 2 times. If the result is 0, it is a perfect Square, else not
@@ryanzullo7169floor() is going to cause losses. you can just do: return (sqrt(N) % 1) == 0. This would work for the most of the reasonable amounts of values for N. sqrt() in code isn't actually a true sqrt() and is just an approximation using fancy math. Plus if N is very large, the amount of bits that sqrt() has access to will be limited. This bit limitation will cause errors for some N that are large enough and are close enough that the precision of a float number wont be able to tell the difference and will mislabel some numbers as squares.
How do you think square root function is programmed? For integers it would be programmed in a very similar way (same time complexity), and for floating point numbers you would have to use something like newton’s method which would be even worse
@@njgskgkensidukukibnalt7372 First of all, if you're using Python, the sqrt can be programmed inside the implementation of the interpreter, likely in C. In such tasks C is likely at least one order of magnitude faster (I'd guess 2 orders of magnitude because of extensive use of loops). Now consider the possibility (spoiler: actually the case) that the CPU can implement the function in the hardware. This is why maybe youtube shorts isn't the best place to learn programming.
taking the sqrt of a number is expensive. that’s why games do approximations instead of calculating the sqrt of numbers. or in cases where you don’t need to explicitly sqrt, you can instead multiply x*x as shown here which is a faster and very easy for computers to do.
just realized Math class probably isn't allowed so here: public boolean isPerfectSquare(int num) { int sum = num-1, x = 0; while (sum < num){ sum = x*x; if (sum == num) return true; x++; } return false; }
@@GregHogg perfect squares are made up of consecutive odd numbers. subtract until you hit 0 or less, if exactly zero then number is a square. There are likely optimisations and mathematical shortcuts
@@drcl7429how u gonna know the number to check if u got a square and not just even number? If u gonna check it your code is already slower than binary search
@@GregHogg I just thought I would contribute my solution to this comment section even though it shares the same time and space complexity with yours, being O(log n) and O(1) respectively.
Here's how i did it: def isPerfSq(a): return a**0.5 - math.floor(a**0.5) == 0 For any number a EDIT: I just realized it's probably better to check if a**0.5 % 1 == 0 but whatever it still works
The problem is that square roots and fractional exponents in general, aren't a very efficient algorithm. They are subject to floating point errors. You might have a near-miss case, where a square root APPEARS to be a perfect integer, but is off by 10^(-16), and it is a blind spot to your code if you use floating point math. The idea is to do this purely with integer operations.
Master Data Structures & Algorithms For FREE at AlgoMap.io!
🎩
😁
👕👍Great!
👖
return (N & (N-1)) == 0
That is not for perfect square.
It is a check for if the number is power of 2 or not@@VedantTinkhede-ei4zb
Can’t you literally just calculate the square root and then see if there’s trailing decimals? That would be O(1)
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
every time this guy pops up on my feed i go to the comments and there's always an explanation for why his algorithm scales like shit
Serious question - where do you learn stuff like this? Had an algorithmic programming class in college but never had to solve problems like this on the job. At a bare minimum, this is fascinating.
@@jackhedaya571 Do you mean me or the channel owner? If you're asking me, then the answer is many, many years using computers to solve number theory problems (I'm not a mathematician, but a mathematically-oriented software engineer).
@@davidgillies620 Yup! Was asking you. Saw the question and immediately thought there needs to be a super fast way of doing it (I was guessing it would be some bit magic).
That's really cool! Can I ask what domain of software you work in? My day-to-day is mostly APIs, DBs, deployments, etc. but a part of me yearns to work on problems that require more clever solutions.
Best way to scale this solution is to see that # of digits in the sqrt(n) is the ceiling of 1/2 the digits in n. Then you can set your binary search range to 10000....99999 (with the number of digits determined by the relation described above). This is true for 100% of cases, no exceptions.
square=sqrt(num)
floor = square//1
return square==floor
I did this in python and beat 97.3%
That's the catch you can't use sqrt function..
@@bharatsahu1599 oh whoops, thx for tellin me
Huh I'll try this too
Sorry wrong answer dude better luck next time
sqrt is expensive
Perfect circles been real quiet since this one dropped
highly underrated comment
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 1000000000, you can start with a range of 10000-99999 instead of 1-500000000.
Btw, I offer personalized 1 on 1 tutoring services for data structures and algorithms / coding interview prep - please email greg.hogg1@outlook.com to book a meeting with me!
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.
You would have to check if N is 1 or 2 first
@@brycejohansen7114 true you'll have to check for just 1, 2 isn't a perfect square. I just assumed people will understand that.
@@shubhambhattacharjee1111 Oops, my bad.
It's log(n), so doesn't matter much
Why only go for 2? If you use N/4 than it still works for every root over 4. If it's less just check with OP's algorithm.
Just do a square root and try to stick the result in a var type int and catch the error. If err != nil { fmt.Println("not perfect square ")}
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.
I think I have one of the fastest leetcode solutions for this one iirc. I cheated and used a taylor series expansion that's done using type coercion in C++ as an initial guess.
Stop lying. I checked the 100 best solutions for this problem and yours is nowhere. You didn't code anything, stop lying
@@joker345172 LOL
Goddamnit why is it always binary search or recursion? xD
Better approach use range from 1 to n/2 (make r= n/2 in this code at start) and do binary search
If I close my eyes ..it feels like shroud teaching coding
Cant we solve it constant times by using bit representation of the number
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
Thanks Greg, I learned new stuffs from you everyday.
It'd probably be much faster to find the number of digits in the representation of the value, and just drop half of them and start you search there. So if N = 405332, don't start with 202666, but with 405. A binary search takes 3 steps to remove a digit from a decimal representation, which could be a lot of steps for a very large number.
you can go from 1 to N/2 and check only those that have the same parity than N.
that speeds it quite a bit for large numbers.
there are other additional methods to speed it even more but are a bit more complex and it's late for me. good night.
You, dear sir, are a perfect square ⏹️
In c++ its too easy, just create an int n, read n from console, calculate sqrt(n) - dont forget to include cmath, create a double variable m = sqrt(n) and of static cast m - n == 0 return true else return false
I am thinking that you can scale all recorded speeds for segments down to a range (0,1] where 1 * speed limit gives you the absolute speed. Also, featurize the historical timestamps into day of week/month, year, season, holiday, etc for those 2 min segments for each day. From this, there are plenty of regression models that are fast enough to be able to put out a (0,1] speed given the features for the actual predicted period/road segment. You can train these on splits with multiple 2 month holdouts to do as many sessions of cross-validation for hyperparameter tuning as you like. Your loss function can be MAE/RMSE/etc for the 2 months of predictions.
Each day, you batch create your predictions for the next day, and they are stored in a fast cache to be used with the existing shortest path function to calculate the ETA.
Uhm, what
@@GregHogg Woops. This comment was supposed to go on a MLSD video. Was wondering why it didn't show up.
I'll post an actually relevant comment in a new thread haha.
If you take a look at the perfect squares you'll notice their progression is as follows:
4-1=3
9-4=5
16-9=7
25-16=9
...
Those are the odd numbers.
So if you want to check if any number is a perfect square you can check if it's part of this progression or not.
just use square root
Yes haha unfortunately the question doesn't allow this
@@GregHogg damn
@@GregHogg It doesn't guarantee perfectly square roots anyway due to finite FP precision.
Best algorithm is probably Newton ralphson method.
...which is ironically exactly what square root is doing.
@@joergsonnenberger6836 yeah but if sqrt() is not allowed for some reason, then this?
cur = 2
while True:
cur = cur * cur
if cur > target:
break
then linearly count down
Isn't this powers of 2 only?
Newton's method for solving the equation x^2 - y = 0. Could work as well and i believe it converges faster.
I always used like x**0.5==int(x**0.5)....
Why such complex thing? Is it more optimal then calculating sqareroot?
does it have to be that fast if the list is that small? at some point you can do the calculations instead or? just if x^2 less or more
I usually use
if( (double)sqrt(n)==(int)sqrt(n) ) cout
Omg very nice. I'll try this next
Awesome thanks so much!
Am I underestimating the problem or...
return round(N**(1/2))**2==N
Is it more efficient to loop through the bits and see if there is only 1 set bit in an even position?
That does not identify square numbers.
No quake fast square root, or that was a different problem?
I love your videos 📸🤩🤩❤❤
Thank you so much 😊😊😊
"sqrt(n) * sqrt(n) == n" left the chat
"No, 1^2 is 2." T. Howard.
And that is why u should use a math library
You can do sqrt of this number and if it is not integer you know that it is not a perfect square.
Lol, best solution wtf
If the sqrt is not allowed simply use the representation of a sqrt which will always be ^(1/2), by doing so and validating if the number is a int, it’ll beat that since its complexity is O(1)
Sqrt operation is not O(1). If i ask you what the sqrt of an arbitrary number is you would need to do an increasing amount of work proportional to the magnitude of the number I chose.
@@njgskgkensidukukibnalt7372 But we assume the size of integer if fixed, e.g. 32bit, 64bit. So the magnitude of a number is constant. Without the assumption, even the method shown in the video will need to handle large numbers, or integers with arbitrary number of bits.
@@user-wt1ul7ki6p ? i dont understand.
The code in the video (and for an integer sqrt program) does a binary search between 0 and n. This will take O(logn). The number of bits needed to represent the number is independent of the number of steps the binary search part will take. What matters is the magnitude of n which is not constant here.
My head : Put it in the square hole
shortest an is = n&(n-1)
return int(n**0.5)==n**0.5
what happened to using something like
if MOD n DIV n = 0
I highly suspect some bitwise trickery would solve this in 2 or 3 operations.
And explain why not just get square root and check if it's a int?
He says sqrt() not allowed.
why not n / 2 / 2?
Why not to use a square root function?
It boils down to there being no pure integer square root CPU instructions under the hood - the simplest is the x87 fsqrt function which yields a floating point result with only around ~23 bits of precision. The bottom line here is that you cannot rely on floating point values because it require equality testing which is non-deterministic due to the lack of precision. Even if you use SSE (32bits of precision) or SS2 (64 bits), this fundamental constraint applies - you cannot be guaranteed that you have enough precision to guarantee a "perfect" square root.
You could of course implement an integer sqrt function (for example Newton's or Heron's method) to appeal to the "understandability" of what you're trying to achieve, but since it is iterative it has a non-linear cost, which happens to be greater than this recursive approach.
cant u just int(sqrt(val)) and if it gives an error (number can't be converted to int, meaning is a decimal number) it isnt a perfect square
In theory it wouldn't work for all N. there could be some N that is close enough to a perfect square that the decimals get truncated after enough places after the sqrt. and int() will truncate any float its given so you'd have to do something else like modulo division to check for decimals.
@@bobmike2373 then u could, instead of int(), just modulo divise the sqrt to itself floored. To do so, u would store the result of the sqrt in a variable so that u don't have to calculate it 2 times. If the result is 0, it is a perfect Square, else not
@@ryanzullo7169floor() is going to cause losses. you can just do:
return (sqrt(N) % 1) == 0.
This would work for the most of the reasonable amounts of values for N. sqrt() in code isn't actually a true sqrt() and is just an approximation using fancy math. Plus if N is very large, the amount of bits that sqrt() has access to will be limited. This bit limitation will cause errors for some N that are large enough and are close enough that the precision of a float number wont be able to tell the difference and will mislabel some numbers as squares.
@@bobmike2373 wont %1 always be == 0? A number, even with decimal values, divided by one is always equals to itself and has rest = 0
@@ryanzullo7169 % is remainder division. x%1 will return the remainder of diving x by 1. so while 5 % 2 = 1, 5 % 3 = 2, 5 % 1 = 0, 5.1 % 1 = 0.1
A = N ** ½
if A % 1 == 0:
print(N, 'is a perfect square')
else:
print(N, 'is not a perfect square')
Yes haha
Not really. Those approximation errors will fuck this up
Is there any video of vertical traversal BST from greg?
No actually I need to cover this question. Adding to my list, thank you
just do this:
return math.sqrt(num)%1 == 0:
you may not use sqrt in this problem
Log(2)base N ??
How About:
n= 17
print(int(n**(1/2)) == n**(1/2))
?
Why not just square root all inputs and check to see if that number has a floating point or a decimal or not?
How do you think square root function is programmed? For integers it would be programmed in a very similar way (same time complexity), and for floating point numbers you would have to use something like newton’s method which would be even worse
@@njgskgkensidukukibnalt7372 First of all, if you're using Python, the sqrt can be programmed inside the implementation of the interpreter, likely in C. In such tasks C is likely at least one order of magnitude faster (I'd guess 2 orders of magnitude because of extensive use of loops). Now consider the possibility (spoiler: actually the case) that the CPU can implement the function in the hardware. This is why maybe youtube shorts isn't the best place to learn programming.
I like this
Thank you!
Cant you just floor it the square root of it and see if thats equal to the square root?
You can do that, but
1. It defeats the purpose of the question
2. It is slower
Why can't you just the root square??
Square root has left the chat
😂
Check if square root is an integer?
Yes you can the problem just doesn't allow this
The idea is to do it purely in integer math, since integers are more efficient in a computer's memory.
Num ** (1/2) ?
Square root?
Int sq_root = Sqrt(N)
Int sq_root_1 = Sqrt(N-1)
If(sq_root > sq_root_1)
Return true
else
Return false
what about using newton's method?
I think the idea is to do this purely in integer math. Integers are more efficient in memory, and less susceptible to rounding errors.
✓17 = int(✓17) does it not work?
If true then it's a perfect square
Why cant you check if floor(sqrt(N))= sqrt(N)?
taking the sqrt of a number is expensive. that’s why games do approximations instead of calculating the sqrt of numbers. or in cases where you don’t need to explicitly sqrt, you can instead multiply x*x as shown here which is a faster and very easy for computers to do.
Thats technically O(n^1/2) which is slower than O(log(n)). So its just not the fastest
Cant you just find the square root and make sure it has no decimals.
uh...
public boolean isPerfectSquare(int num) {
if (Math.sqrt(num) % 1 == 0) return true;
return false;
}
7ms runtime.
just realized Math class probably isn't allowed so here:
public boolean isPerfectSquare(int num) {
int sum = num-1, x = 0;
while (sum < num){
sum = x*x;
if (sum == num) return true;
x++;
}
return false;
}
Yes this would work the problem just doesn't allow this idea unfortunately
@@kyledouglass7683 so basicly its linear approach. In video he talked about it and did binary cuz linear is O(n) and binaey is O(log n)
Someone count voice cracks quick
def is_perfect_square(N):
t = 1
while N>0:
N-=t
t+=2
return N==0
I just solved this question 😂
I still don't get what's a perfect square 😂
Just square root it lmao or if thats not possible on python take 16 to the power of 0.5 (same thing as square rooting)
That is slower, although in practice it may be better to do that for readability
Just take the sqrt btw
Absolutely in the real world. But this problem statement happens to not allow this solution
I don't like when i am early...
How is this a Microsoft coding question?!
if (sqrt(n)%1 == 0) {
return “yes”;
} else {
return “no”;
}
Thafuq? unsigned long t = (unsigned long) floor(0.5 + sqrt(x)); return x == t*t;
Dude… just do
return sqrt(x) % 1 == 0;
you look like jeb
I "like" how the author doesn't address the elephant in the room (sqrt) to bait comments to game the youtube algorithm...
Not baiting. The problem statement doesn't allow this solution. So I didn't bother mentioning it
@@GregHogg But the viewer doesn't know that if you don't mention it :D
sum of odd numbers anyone?
What?
@@GregHogg perfect squares are made up of consecutive odd numbers. subtract until you hit 0 or less, if exactly zero then number is a square.
There are likely optimisations and mathematical shortcuts
@@drcl7429how u gonna know the number to check if u got a square and not just even number? If u gonna check it your code is already slower than binary search
Woww, is this true for all perfect squares? @@drcl7429
@@drcl7429 wow that beautiful
Much easier to just check that the number in binary has only one bit set
That only works for powers of 2
二分法
pow(sqrt(N),2) == N
this is an interview question but they cant make a good OS to save their lives
Lol windows has its issues and always will but I still like it
@GregHogg they really struggle with the "just make xp but better" concept
return n >= 0 and math.isqrt(n) ** 2 == n
Is that actually a function?
@@GregHogg I just thought I would contribute my solution to this comment section even though it shares the same time and space complexity with yours, being O(log n) and O(1) respectively.
Here's how i did it:
def isPerfSq(a):
return a**0.5 - math.floor(a**0.5) == 0
For any number a
EDIT: I just realized it's probably better to check if a**0.5 % 1 == 0 but whatever it still works
Excellent
def checksqure(n):
if str(n**0.5).endswith('.0'):
return True
else:
return False
The problem is that square roots and fractional exponents in general, aren't a very efficient algorithm. They are subject to floating point errors. You might have a near-miss case, where a square root APPEARS to be a perfect integer, but is off by 10^(-16), and it is a blind spot to your code if you use floating point math.
The idea is to do this purely with integer operations.