One optimization can be also to track not only start/end but also power of start/power of end. So we don't need to recalculate power of start when we change end, or recalculate power of end when we change start. So save one multiplication on each iteration. Still constant space but saving on each iteration.
I haven't seen his solution (I think it is good or ok) My solutions are either. A.) Uses some sort of Binary Search. Like starting min is 0 to max c. B.) Uses sliding window? I think there's a lot of solutions to this problem. And should be interesting.
my solution, like your first one but with O(1) SC: if c == 0: return True for a in range(ceil(sqrt(c))): b = sqrt(c - a * a) if b % floor(b) == 0: return True return False
The prime divisors of the squarefree part of c must all be 1 mod 4. If c is 3 mod 4, you can automatically rule it out. 9 evaluates to true by the way since 3^2+0^2=9.
we do not allow 2 same integers (0:39) technically for 8 it is not 2 and 2, it is 2 and -2. We are squarring the numbers so obviously there wont be a difference. And for 9 it should be true because 3^2 + 0^2 is 9
Actually we don't really need the Hashset in the first solution, simply check if b is perfect square or not, we can check if a number is perfect square by comparing the floor and ceil of sqrt(number) : potential_b = sqrt(c - a^2) if floor(potential_b) == ceil(potential_b): return True
Hey, how do you realize that it's gonna pass the time complexity? I saw 2^31 and that's about 10^9 So I thought it gotta be a O(1) or O(n) solution Got stuck there and didn't even think of brute force
Dude You are complicating the solution. Below is my solution. class Solution: def judgeSquareSum(self, c: int) -> bool: for a in range(int(c ** 0.5) + 1): b = (c - a ** 2) ** 0.5 if b == int(b): return True return False
I think 9 should also be true as 3^2 + 0^2 is 9.
Well it depends if we can include 0 in I j or not
@@maanas_sehgal Well it is given in the constraint
Buddy it's a^2 + b^2 so it can be only a and b
In 3^2 and 0^2 there are three integers
Wtf@@02devavratkumarmahato11
One optimization can be also to track not only start/end but also power of start/power of end. So we don't need to recalculate power of start when we change end, or recalculate power of end when we change start. So save one multiplication on each iteration. Still constant space but saving on each iteration.
I came up with similar solution but my mistake was that I initialized r with c instead of sqrt of c, which got me into TLE.
I haven't seen his solution (I think it is good or ok)
My solutions are either.
A.) Uses some sort of Binary Search.
Like starting min is 0 to max c.
B.) Uses sliding window?
I think there's a lot of solutions to this problem. And should be interesting.
my solution, like your first one but with O(1) SC:
if c == 0: return True
for a in range(ceil(sqrt(c))):
b = sqrt(c - a * a)
if b % floor(b) == 0:
return True
return False
W title
I was waiting for this one
The prime divisors of the squarefree part of c must all be 1 mod 4.
If c is 3 mod 4, you can automatically rule it out.
9 evaluates to true by the way since 3^2+0^2=9.
we do not allow 2 same integers (0:39) technically
for 8 it is not 2 and 2, it is 2 and -2. We are squarring the numbers so obviously there wont be a difference.
And for 9 it should be true because 3^2 + 0^2 is 9
How about for 0 then?
Incredible solutioN!
thanks
smooth AF
Actually we don't really need the Hashset in the first solution, simply check if b is perfect square or not, we can check if a number is perfect square by comparing the floor and ceil of sqrt(number) :
potential_b = sqrt(c - a^2)
if floor(potential_b) == ceil(potential_b):
return True
Solved it!!
Good video!
You can reverse the title of this video so the others can find this video easier
great solution
Hey, how do you realize that it's gonna pass the time complexity?
I saw 2^31 and that's about 10^9
So I thought it gotta be a O(1) or O(n) solution
Got stuck there and didn't even think of brute force
Hi, why do you not make videos about the 2 hard problems they asked yesterday and the day before? Just curious
I think i already made a video for IPO. For the second one I was out of town unfortunately
The cooler 2 sum problem.
def soluion(c):
s = set()
for a in range(int(sqrt(c))+1):
sqr = a*a
s.add(sqr)
if c-sqr in s: return True
return False
Excitedly I added this solution before the video could end, thinking I outsmarted you, until I saw the last solution
I'm just gonna throw it out there. But
If A or B is 0 then the other letter must be a perfect square.
If there is no perfect square then it is false.
🎉🎉
What's up with the title?
Dude You are complicating the solution. Below is my solution.
class Solution:
def judgeSquareSum(self, c: int) -> bool:
for a in range(int(c ** 0.5) + 1):
b = (c - a ** 2) ** 0.5
if b == int(b):
return True
return False
I think you forgot to change the title before publishing.
Wow, how did I miss ua-cam.com/video/B0UrG_X2faA/v-deo.html!