Sum of Square Numbers - Leetcode 633 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
5:25 - Coding Explanation
7:54 - Drawing Explanation 2
13:08 - Coding Explanation 2

leetcode 633

#neetcode #leetcode #python

[AnordinaryMan]

I think 9 should also be true as 3^2 + 0^2 is 9.

[MykolaPavluchynskyi]

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.

[dhaanaanjaay]

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.

[asagiai]

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.

[hoyinli]

Good video!

You can reverse the title of this video so the others can find this video easier

[inferno]

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

[bedokhaled]

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

[galkk]

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

[jersefrenzer]

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.

[optimistcarrot]

Hi, why do you not make videos about the 2 hard problems they asked yesterday and the day before? Just curious

[ngneerin]

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

[Karan-ghki]

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

[asagiai]

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.

[LIGHTsoldier]

I think you forgot to change the title before publishing.

[freecourseplatformenglish]

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